1 · Model, solve and test · 25 MIN

Count peak overlap with event ordering

Count peak overlap with event ordering

An interval can be represented by a start event and an end event. Sort events by time and sweep a running active count. For half-open intervals, an end at time t must be processed before a start at t, so touching reservations do not overlap. Ignore zero-length intervals. This converts many pairwise comparisons into one sort and one scan. The example accepts valid start <= end pairs and numeric times.

Sort equal-time end events before start events.

Read the example

function solve(input){const events=[];for(const [start,end] of input){if(start<end){events.push([start,1],[end,-1])}}events.sort((a,b)=>a[0]-b[0]||a[1]-b[1]);let active=0,peak=0;for(const [,delta] of events){active+=delta;peak=Math.max(peak,active)}return peak}
console.log(JSON.stringify(solve([[1,4],[2,5],[4,6]])));

2

Your challenge

Return the maximum number of simultaneously active half-open intervals [start,end). Zero-length intervals contribute nothing; touching endpoints do not overlap.

Solution cost: O(n log n) event sorting. time · O(n) events. space

Common trap

Processing starts before ends at a tied time overcounts touching half-open intervals.