Meetings sorted by start · yellow: in progress at the sweep line · grey: over
start sorted start times
end sorted end times
rooms green: busy now · outlined: needed at some point (res)
public int minMeetingRooms(List<Interval> intervals) { int n = intervals.size(); int[] start = new int[n]; int[] end = new int[n]; for (int k = 0; k < n; k++) { start[k] = intervals.get(k).start; end[k] = intervals.get(k).end; } Arrays.sort(start); Arrays.sort(end); int res = 0; int count = 0; int s = 0; int e = 0; while (s < n) { if (start[s] < end[e]) { // a meeting begins s++; count++; } else { // one ends first (or at the same time) e++; count--; } res = Math.max(res, count); } return res;}
- s, e
- —
- start[s], end[e]
- —
- count
- 0
- res
- 0
Why it works
- Brute force counts overlaps at every start time: for each meeting, count the meetings in progress when it starts, and take the max. O(n²).
- Only the events matter, not which meeting they belong to. Walk the start and end times in time order: a start takes a room (
count += 1), an end frees one (count -= 1). The answer is the highestcountever reached. - Cost: two sorts, O(n log n), then each pointer moves at most n times, O(n). The two sorted arrays take O(n) space.
- Pitfall: on a tie, process the end first.
start[s] < end[e]is strict, so[1,5]and[5,10]share one room instead of needing two. - Alternative: sort by start and keep a
PriorityQueue(min-heap) of end times; pop the root when it ends by the next start. The heap's largest size is the answer, also O(n log n).