1448. The Most Jobs Running at Once

n jobs are given. Job i occupies the HALF-OPEN stretch [a, b) with a < b: it is running from time a up to but NOT including time b. A job that ends at time t and a job that starts at time t are never running at the same moment.

Print the largest number of jobs running simultaneously at any one moment.

[1,5) [2,6) [8,9) [3,4) -> 3 at time 3 the first three of those overlap [1,3) [3,5) [5,7) -> 1 they hand over, never sharing a moment [0,10) [0,10) [0,10) -> 3

The middle line is the convention. Under a CLOSED reading those three jobs would overlap in pairs at times 3 and 5 and the answer would be 2. Half-open means a handover is clean, and that is why scheduling software almost always uses it.

## What most people try first

Comparing every pair of jobs and counting overlaps. That gives the largest number of jobs overlapping SOME OTHER job, which is not the same question: five jobs can pairwise overlap without any single moment holding all five. It is also O(n^2), which is 4 * 10^10 pair tests at n = 200000.

The second reflex is to walk time one unit at a time counting who is running. Times reach 10^9 in both directions, so there are up to 2 * 10^9 moments.

## Two events per job, sorted

Nothing changes between events, so only the events matter:

for each job [a, b): event(a, +1) and event(b, -1) sort by coordinate; at equal coordinates put -1 BEFORE +1 running = 0, best = 0 for each event in order: running += its delta best = max(best, running)

Sorting 2n events is O(n log n), about 7 * 10^6 comparisons at the limits, and the walk is one pass.

## The tie-break IS the convention

At a coordinate holding both an end and a start, the order decides the answer. Processing the -1 first means the ending job has already left when the starting job arrives, which is exactly what [a, b) says. Processing the +1 first would count them together for an instant and report 2 on the middle sample instead of 1.

So sort by (coordinate, delta) with -1 < +1. This is not a detail that can be left to the sort's default behaviour: swap it and every answer in the second sample changes.

## Why the running count is right

Read the events left to right. Before any event the count is 0. After processing every event at or before a coordinate x, the count equals the number of jobs with a <= x minus the number with b <= x, which is exactly the number of jobs with a <= x < b: the jobs running at x. So every value the counter takes is a real simultaneous count, and the maximum over the walk is the maximum over all time.

## Overflow

The answer is at most n = 200000, so it fits in a signed 32 bit integer many times over. The coordinates reach 10^9, also inside the 2147483647 limit. This problem has no overflow to guard against; the next few in the block do.

## Related

Problem 277 asks the same question about trains under the CLOSED reading, where a train arriving as another departs still needs its own platform, and gets the arrival and departure times as two separate lists. Problem 1459 prints both answers side by side so the two conventions can be compared on one input. Problem 1479 adds the coordinate at which the maximum first occurs.

Constraints - `1 ≤ n ≤ 200000` - `-10^9 ≤ a < b ≤ 10^9` - each job occupies the half-open stretch `[a, b)`, so a job ending at `t` and one starting at `t` never run together - jobs arrive in no particular order