Merge Intervals

---

Merge Intervals: Given an array of intervals where intervals[i] = [start_i, end_i], merge all overlapping intervals, and return an array of the non-overlapping intervals that cover all the intervals in the input.

Example 1:

Input: intervals = [[1,3],[2,6],[8,10],[15,18]]
Output: [[1,6],[8,10],[15,18]]
Explanation: Since intervals [1,3] and [2,6] overlap,
merge them into [1,6].

---

Example 2:

Input: intervals = [[1,4],[4,5]]
Output: [[1,5]]
Explanation: Intervals [1,4] and [4,5] are considered overlapping.

---

Constraints:

• 1 <= intervals.length <= 10^4
• intervals[i].length == 2
• 0 <= start_i <= end_i <= 10^4

---

Try this Problem on your own or check similar problems:

1. Teemo Attacking
2. Insert Interval
3. Divide Intervals Into Minimum Number of Groups
4. Range Module
5. Count Integers in Intervals

Solution:

Java

public int[][] merge(int[][] intervals) {
    Arrays.sort(intervals, (a,b) -> a[0] - b[0]);
    int[] interval = intervals[0];
    List<int[]> result = new ArrayList<>();

    for(int i = 1; i < intervals.length; ++i){
        if(interval[1] >= intervals[i][0]){
            interval[1] = Math.max(interval[1], intervals[i][1]);
        }
        else{
            result.add(interval);
            interval = intervals[i];
        }
    }
    result.add(interval);
    return result.toArray(new int[result.size()][]);
}

JavaScript

/**
 * @param {number[][]} intervals
 * @return {number[][]}
 */
var merge = function (intervals) {
  intervals.sort((a, b) => a[0] - b[0]);
  let interval = intervals[0];
  const result = [];

  for (let i = 1; i < intervals.length; ++i) {
    if (interval[1] >= intervals[i][0]) {
      interval[1] = Math.max(interval[1], intervals[i][1]);
    } else {
      result.push(interval);
      interval = intervals[i];
    }
  }

  result.push(interval);
  return result;
};

Python

class Solution:
    def merge(self, intervals: List[List[int]]) -> List[List[int]]:
        intervals.sort(key=lambda x: x[0])
        interval = intervals[0]
        result = []

        for i in range(1, len(intervals)):
            if interval[1] >= intervals[i][0]:
                interval[1] = max(interval[1], intervals[i][1])
            else:
                result.append(interval)
                interval = intervals[i]

        result.append(interval)
        return result

C++

class Solution {
public:
    vector<vector<int>> merge(vector<vector<int>>& intervals) {
        std::sort(intervals.begin(), intervals.end(), [](const std::vector<int>& a, const std::vector<int>& b) {
            return a[0] < b[0];
        });

        std::vector<int> interval = intervals[0];
        std::vector<std::vector<int>> result;

        for (int i = 1; i < intervals.size(); ++i) {
            if (interval[1] >= intervals[i][0]) {
                interval[1] = std::max(interval[1], intervals[i][1]);
            } else {
                result.push_back(interval);
                interval = intervals[i];
            }
        }

        result.push_back(interval);
        return result;
    }
};

---

Time/Space Complexity:

• Time Complexity: O(nlogn) where n is the number of intervals (n = intervals.length)
• Space Complexity: O(1)

---

Explanation:

We first sort the intervals by their start time and choose the first interval in the sorted array as our first interval we want to merge other intervals with. We iterate over other intervals each time checking if we can merge them with the current interval, we do this by checking if the end of our current interval is larger than the start of the next interval which means there is an intersection, and we can merge them. How do we choose the end time for our new interval? Well, the end time is the maximum of the current interval end time and the next interval (the one we're trying to merge with) end time. If there is no intersection, we add the merged interval to the result and choose the current loop interval as the next interval we want to merge other intervals with. Finally, we return the result (converted from list of arrays to array of arrays). The time complexity is equal to the complexity required to sort the array of intervals.