Maximum number of overlapping Intervals

JavaView on GFG

Problem Overview

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

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?