1479. Fewest Rooms, and the Moment That Proves It

n sessions are given, session i occupying the HALF-OPEN stretch [a, b) with a < b. Sessions are to be split into GROUPS so that no two sessions in one group overlap; sessions that merely touch may share a group.

Print two integers on one line: the fewest groups, and the EARLIEST coordinate at which that many sessions are running at the same time.

[1,5) [2,6) [8,9) [3,4) -> 3 3 [1,3) [3,5) [5,7) -> 1 1 [0,5) [0,5) [0,5) [0,5) -> 4 0

The second number is not decoration. It is a CERTIFICATE: it names a single moment at which the stated number of sessions are all running, which proves that no smaller number of groups can possibly work, because those sessions pairwise overlap and no two of them may share a group.

The middle line is the endpoint rule. The three sessions hand over cleanly, so only one is ever running, one group suffices, and the earliest moment with one session running is 1.

## What most people try first

Simulating the grouping: sort by start, keep the end time of each group, and put each session in a group that has finished. That gives the right number and no witness, and it is O(n^2) if the groups are scanned or O(n log n) with a heap. It is problem 1478, and it is doing work this question does not need.

The second attempt is to report, as the witness, the start of the session that created the last group. That is a moment at which that many sessions are running, but not necessarily the EARLIEST one, because a later session can be the one that forces a new group while an earlier moment already carried the same number.

## Sweep once and record where the peak first appears

for each session [a, b): event(a, +1) and event(b, -1) sort by coordinate; at equal coordinates put -1 BEFORE +1 count = 0; best = 0; at = 0 for each distinct coordinate x, in order: apply every event at x if count > best: best = count; at = x print best, at

O(n log n). There are no groups anywhere in the code, and that is the point.

## Why the peak is the number of groups

Two directions.

The peak is a LOWER bound. If k sessions are running at one moment, then every pair of them overlaps, so no two may share a group, so at least k groups are needed.

The peak is ACHIEVABLE. Process the sessions in increasing order of start and hand each one to any group whose last session has already ended. If at some point no group is available, every existing group is holding a session that started at or before the current a and ends strictly after it, so all of those sessions, together with the current one, are running at a. That means the peak is at least (number of groups so far) + 1, so a new group is only ever opened when the peak grows. The number of groups therefore never exceeds the peak.

Together: fewest groups equals maximum concurrency. This is the whole reason interval scheduling problems collapse to counting.

## Why the earliest such coordinate is a start coordinate

The count only ever rises at a session start, so the first moment at which a new record is reached is one of the a values. Recording a new best only on a strict improvement, and taking the coordinate at which it happened, gives the earliest one. Using >= would report the last coordinate holding the peak, which is a different question.

## Overflow

Counts are at most n = 200000 and the witness is a coordinate of magnitude at most 10^9, both inside the 2147483647 a signed 32 bit integer holds. Nothing accumulates.

## Related

Problem 1477 asks only for the number of groups, with a cleaning gap added. Problem 1478 carries out the assignment and reports how crowded the busiest group gets. Problem 1480 asks the same equivalence about pairs under the strict-chain rule, where the same theorem goes by the name of Dilworth.

Constraints - `1 ≤ n ≤ 200000` - `-10^9 ≤ a < b ≤ 10^9` - each session occupies the half-open stretch `[a, b)`, so sessions that merely touch may share a group - sessions arrive in no particular order and may repeat