NeetCode #839LC-2406MediumIntervals
← Back to All Problems#839 · #2406 · Divide Intervals Into Minimum Number of Groups(将区间分为最少组数)
📌 Problem Statement & Constraints
You are given a 2D array
intervals. Divide the intervals into the minimum number of groups such that no two intervals in the same group overlap. Two intervals overlap if they share at least one point. Return the minimum number of groups. Constraints: 1 <= intervals.length <= 10^5, 1 <= left <= right <= 10^6.💡 Core Algorithmic Approaches
- The minimum number of groups equals the maximum number of intervals that overlap at any single point.
- Model each interval as a start event
+1and an end event-1placed one past the end, then sort all events by position. - Sweep the events accumulating the running count; the maximum count is the answer.
- The
end + 1placement is what makes touching intervals (which share an endpoint) count as overlapping.
💻 Benchmark Python3 Implementation
class Solution:
def minGroups(self, intervals: List[List[int]]) -> int:
events = []
for l, r in intervals:
events.append((l, 1))
events.append((r + 1, -1)) # intervals are closed
events.sort() # on ties, -1 sorts before +1
cur = ans = 0
for _, d in events:
cur += d
ans = max(ans, cur)
return ans⚡ Complexity Deep Dive
⏱️ Time Complexity
O(n log n): sorting the 2n events dominates.
💾 Space Complexity
O(n): the events array.
⚠️ Interview Pitfalls & Follow-ups
- Placing the end event at
rinstead ofr + 1: closed intervals that touch share a point and overlap, so the decrement must come after the point. - Placing the end event before the start on ties: with
(time, delta)sorting,-1precedes+1, which is exactly right for closed intervals ending where another begins. - Trying to greedily assign groups: a per-interval greedy is error-prone; the peak-overlap characterisation is exact.
- Confusing this with
253: the answer is the same quantity, but here intervals are closed, so the event placement differs.
⚡
Test muscle memory on this topic via 3-Layer Flashcards
Active Recall: Mentally formulate Prompt ➔ Math Derivation ➔ Benchmark Implementation in 3 minutes.