Sweep Line / Event Counting
Turn each interval into a start event of plus one and an end event of minus one, sort the events and track the running total.
IntervalsO(n log n)New5 problems
18
mastery
Trigger phrases
If a problem statement sounds like one of these, try this pattern first.
max concurrent meetings
car pooling capacity
skyline
The template
Get this into muscle memory, then adapt the condition per problem.
const ev: [number, number][] = [];
for (const [s, e] of iv) { ev.push([s, 1]); ev.push([e, -1]); }
ev.sort((a, b) => a[0] - b[0] || a[1] - b[1]);
let cur = 0, best = 0;
for (const [, d] of ev) { cur += d; best = Math.max(best, cur); }If you are stuck
The generic hint ladder for this pattern, in order.
- 1You care about how many intervals are active at a moment, not the intervals themselves.
- 2Ends should be processed before starts at the same timestamp when touching is allowed.
- 3The running counter peak is the answer.
Drill it
Every problem in the bank that uses this pattern.
0 / 5 solved