Intervals

Sweep Line

Mark +1 at each interval's start and -1 at each interval's end. Sort these events by time and walk through them, keeping a running count. The peak count tells you the maximum number of overlapping intervals.

O(n log n)

O(n)

say this out loud

The question is how many overlap at once, so I split each interval into a start and an end event, sort the events, and sweep a running counter.

How It Works

Sweep line converts intervals into point events: a +1 event at each start and a -1 event at each end. Sort all events by time and walk through them left to right, maintaining a running counter of currently active intervals. The counter's peak is the maximum simultaneous overlap. The minimum number of meeting rooms, platforms, or servers needed.

Comparing every interval against every other costs O(n²); the sweep pays O(n log n) for the sort and then a linear scan. Tie-breaking matters: if an interval ends exactly when another begins and they should not count as overlapping, process the -1 event first. When coordinates are small integers, a difference array plus prefix sum achieves the same result without sorting.

Step-by-Step Visualization

Meetings [0,30], [5,10], [15,20]. Split each into two events: a start of +1 and an end of -1

-1

events6

1/10

Code

Java

static int meetingRooms(int[][] intervals) {
  List<int[]> events = new ArrayList<>();
  for (int[] iv : intervals) {
    events.add(new int[]{iv[0], 1});
    events.add(new int[]{iv[1], -1});
  }
  events.sort((a, b) -> a[0] != b[0] ? a[0] - b[0] : a[1] - b[1]);

  int rooms = 0, maxRooms = 0;
  for (int[] e : events) {
    rooms += e[1];
    maxRooms = Math.max(maxRooms, rooms);
  }
  return maxRooms;
}

Tips & Gotchas

1Create events: +1 at each interval start, -1 at each interval end

2Sort events. Sweep through, maintaining a running count

3Max count = max concurrent intervals

Practice Problems

1Meeting Rooms II
2Car Pooling
3My Calendar III
4The Skyline Problem

About the Intervals Pattern

Problems involving ranges [start, end]. Meetings, schedules, overlapping segments. The key first step is almost always: sort by start time (or end time). Then process them linearly.

Key insight

When you see 'subarray', 'contiguous', or 'in-place', think arrays. The key is reducing brute-force O(n²) to O(n) using sliding window, two pointers, or prefix sums.

Common Array Interview Problems

Two Sum
Best Time to Buy & Sell Stock
Maximum Subarray
Merge Intervals
Product of Array Except Self
Container With Most Water

Frequently Asked Questions

How is the sweep line different from merging intervals?

Merging asks only whether ranges touch and outputs coalesced ranges; the sweep counts how many are active at each instant, capturing depth of overlap that merging discards. Use the sweep whenever the question involves 'at the same time'. Rooms, bandwidth, passengers.

When should I use a difference array instead of sorted events?

If timestamps are bounded small integers (say stops along a route in Car Pooling) allocate an array, apply +count at each start and -count at each end, then prefix-sum it. That is O(n + range) with no sorting, but it breaks down when coordinates are large or fractional.

How do I handle an interval ending exactly when another starts?

Decide whether a shared endpoint counts as overlap, then order the events accordingly: process departures before arrivals at equal timestamps if touching does not overlap. Getting this tie-break wrong inflates or deflates the peak count by one in edge cases.