56. Merge Intervals

Intuition

Given an array of intervals, the goal is to merge overlapping intervals to produce a list of non-overlapping intervals that cover all intervals in the input.

Approach

1. Sorting: First, sort the intervals based on the starting value of each interval. This helps in easily identifying and merging overlapping intervals.
2. Merging Intervals: Initialize an empty list to store merged intervals. Iterate through the sorted intervals: - If the current interval overlaps with the last interval in the result list (i.e., current_start <= last_end), merge them by updating the end of the last interval to the maximum of current_end and last_end. - If there's no overlap, simply append the current interval to the result list.
3. Return: The result list now contains non-overlapping intervals that cover all intervals in the input.

Complexity

Time Complexity:

O(n log n) due to sorting, where n is the number of intervals. The merging process takes linear time O(n).

Space Complexity:

O(n) for storing the result list of intervals.

Code

C++

class Solution {
public:
    vector> merge(vector>& intervals) {
        sort(intervals.begin(), intervals.end(), [](const vector& a, const vector& b) {
            return a[0] < b[0];
        });
        vector> res;
        res.push_back({intervals[0][0], intervals[0][0]});
        int lastIdx = 0;
        for (const auto& interval : intervals) {
            int s = interval[0];
            int e = interval[1];
            if (s <= res[lastIdx][1]) {
                if (e > res[lastIdx][1]) {
                    res[lastIdx][1] = e;
                }
            } else {
                res.push_back({s, e});
                lastIdx++;
            }
        }
        return res;
    }
};

Python

class Solution:
    def merge(self, intervals: List[List[int]]) -> List[List[int]]:
        intervals.sort(key=lambda x: x[0])
        result = []
        result.append([intervals[0][0], intervals[0][1]])
        lastIdx = 0
        for interval in intervals:
            s, e = interval
            if s <= result[lastIdx][1]:
                if e > result[lastIdx][1]:
                    result[lastIdx][1] = e
            else:
                result.append([s, e])
                lastIdx += 1
        return result

Java

import java.util.*;

class Solution {
    public int[][] merge(int[][] intervals) {
        Arrays.sort(intervals, Comparator.comparingInt(a -> a[0]));
        List result = new ArrayList<>();
        result.add(new int[] { intervals[0][0], intervals[0][0] });
        int lastIdx = 0;
        for (int[] interval : intervals) {
            int s = interval[0];
            int e = interval[1];
            if (s <= result.get(lastIdx)[1]) {
                if (e > result.get(lastIdx)[1]) {
                    result.get(lastIdx)[1] = e;
                }
            } else {
                result.add(new int[] { s, e });
                lastIdx++;
            }
        }
        return result.toArray(new int[result.size()][]);
    }
}

JavaScript

const merge = (intervals) => {
  intervals = intervals.sort((a, b) => a[0] - b[0]);
  let res = [[intervals[0][0], intervals[0][0]]];
  let lastIdx = 0;
  for (const [s, e] of intervals) {
    if (s <= res[lastIdx][1]) {
      if (e > res[lastIdx][1]) {
        res[lastIdx][1] = e;
      }
    } else {
      res.push([s, e]);
      lastIdx++;
    }
  }
  return res;
};