Merge Overlapping Intervals, thesarfo

Merge all overlapping intervals into the minimum number of non-overlapping ones. (LeetCode 56) For [(1,3),(2,6),(8,9),(8,10),(2,4),(15,18),(16,17)], the answer merges down to 3 intervals: (1,6), (8,11), (15,18).

Approach: sort intervals by start time. Two intervals are mergeable if the next one’s start is <= the current merged interval’s end (in which case extend the end); otherwise, close out the current interval and start a new one.

public int[][] merge(int[][] intervals) {
    if (intervals.length == 0) {
        return new int[0][];
    }

    Arrays.sort(intervals, (a, b) -> a[0] - b[0]);

    List<int[]> ans = new ArrayList<>();

    for (int[] interval : intervals) {
        if (ans.isEmpty() || interval[0] > ans.get(ans.size() - 1)[1]) {
            ans.add(interval);
        } else {
            ans.get(ans.size() - 1)[1] = Math.max(ans.get(ans.size() - 1)[1], interval[1]);
        }
    }

    return ans.toArray(new int[ans.size()][]);
}

Time: O(n log n) for the sort + O(n) for the single merge pass. Space: O(n).