Maximum number of overlapping Intervals

JavaView on GFG

Intuition

Find maximum number of intervals that overlap at any single point. Sweep line.

Algorithm

1Events: +1 at start, -1 at end+1. Sort events, process in order, track running sum maximum.

Common Pitfalls

•Sweep line with events. Sort starts/ends separately or together. Running counter max gives answer.

Maximum number of overlapping Intervals.java

Java

// Approach: Event sweep. Mark +1 at start, -1 at end+1. Max prefix sum is max overlap.
// Time: O(n log n) Space: O(n)
import java.util.*;

class Solution {
    public static int overlapInt(int[][] arr) {
        int[] start = new int[arr.length];
        int[] end = new int[arr.length];

        for (int i = 0; i < arr.length; i++) {
            start[i] = arr[i][0];
            end[i] = arr[i][1];
        }

        Arrays.sort(start);
        Arrays.sort(end);

        int i = 0;
        int j = 0;
        int overlap = 0;
        int maxOverlap = 0;
        while (i < start.length && j < end.length) {
            if (start[i] <= end[j]) {
                overlap++;
                maxOverlap = Math.max(overlap, maxOverlap);
                i++;
            } else {
                overlap--;
                j++;
            }
        }
        
        return maxOverlap;
    }
}

Was this solution helpful?