Overlapping Intervals

JavaView on GFG

Intuition

Find maximum overlap of intervals at any point. Sweep line or sort by start.

Algorithm

1Sort starts and ends separately. Two pointer sweep: increment count on start, decrement on end. Track max.

Common Pitfalls

•Same as "meeting rooms II" (LC 253). Sort starts and ends. O(n log n).

Overlapping Intervals.java

Java

// Approach: Sort by start time. Merge overlapping intervals by extending end when current start <= prev end.
// Time: O(n log n) Space: O(n)
import java.util.*;

class Solution {
    public ArrayList<int[]> mergeOverlap(int[][] arr) {
        Arrays.sort(arr, (i, j) -> Integer.compare(i[0], j[0]));
        ArrayList<int[]> ans = new ArrayList<>();
        int i = 0, n = arr.length;
        while (i < n) {
            int j = i + 1;
            while (j < n && arr[j][0] <= arr[i][1]) {
                arr[i][1] = Math.max(arr[i][1], arr[j][1]);
                j++;
            }
            ans.add(arr[i]);
            i = j;
        }

        return ans;
    }
}

Was this solution helpful?