Peak staffing window
A depot lists staff shifts as integer start and end minutes from midnight. A shift includes its start but not its end, so a shift ending exactly when another begins does not overlap it. Print the maximum number of staff simultaneously on duty and the earliest minute when that maximum begins.
Input
First line N. Next N lines: start end, with start < end.
Output
Two integers on one line: maximum_active earliest_minute.
Example 1
Input
3 9 12 10 13 12 14
Output
2 10
Two people first overlap at minute 10. The handover at 12 still has two, not three.
Constraints
- 1 <= N <= 200
- 0 <= start < end <= 1440
- All times are whole minutes
Hints
Hint 1 of 3
Represent each start as +1 and each end as -1.
Hint 2 of 3
Sort event minutes; no need to inspect every minute of the day.
Hint 3 of 3
Aggregate all changes at the same minute before comparing with the current peak.
Solution
Show a reference solution and explanation
const n = Number(readline());
const events = [];
for (let i = 0; i < n; i++) {
const [start, end] = readline().split(' ').map(Number);
events.push([start, 1], [end, -1]);
}
events.sort((a, b) => a[0] - b[0]);
let active = 0, peak = 0, earliest = 0;
for (let i = 0; i < events.length;) {
const minute = events[i][0];
while (i < events.length && events[i][0] === minute) {
active += events[i][1];
i++;
}
if (active > peak) {
peak = active;
earliest = minute;
}
}
console.log(peak, earliest);
Why it works
The event sweep changes the active count only where a shift starts or ends. Grouping equal-minute events ensures a handover never counts as an overlap. Scan minutes in increasing order and update the answer only when the active count is strictly greater than the previous peak; that preserves the earliest tied minute. Sorting costs O(N log N) and the scan costs O(N).
Lesson for this exercise: JavaScript Arrays: Creating, Indexing and Changing Lists