LeetCode-in-All

56. Merge Intervals

Medium

Given an array of intervals where intervals[i] = [starti, endi], 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 <= 104
• intervals[i].length == 2
• 0 <= starti <= endi <= 104

Solution

class Solution {
  List<List<int>> merge(List<List<int>> intervals) {
    // Sort the intervals based on the start time
    intervals.sort((a, b) =>a[0].compareTo(b[0]));

    List<List<int>> merged = [];
    List<int> current = intervals[0];
    merged.add(current);

    for (List<int> next in intervals){
      if (current[1] >= next[0]) {
        // If the intervals overlap, merge them
        current[1] = current[1] > next[1] ? current[1] : next[1];
      } else {
        // Otherwise, move to the next interval
        current = next;
        merged.add(current);
      }
    }

    return merged;
  }
}

This site is open source. Improve this page.