Overlapping Intervals

JavaView on GFG

Problem Overview

Find maximum overlap of intervals at any point.

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?