#218MediumIntervals· Sweep Line over Start and End Events

Peak Concurrent Streams

A video platform logs every live stream as a half-open interval `[start, end)` of seconds: the stream is running at second `start` and no longer running at second `end`. The capacity team wants to know how many servers they need, which is the largest number of streams that are running at the same moment. Given the log, return that maximum. A stream that ends at second `t` does not overlap a stream that starts at second `t`.

Input format

`intervals`: an array of `[start, end]` pairs, in no particular order.

Output format

A single integer: the maximum number of streams running at the same time.

Examples

Input: intervals = [[0, 30], [5, 10], [15, 20]]

Output: 2

The long stream overlaps each of the other two, but those two never overlap each other, so at most two streams run together.

Input: intervals = [[1, 2], [2, 3], [3, 4]]

Output: 1

Every stream ends exactly when the next one starts. Half-open intervals do not overlap, so the peak is 1.

Input: intervals = [[1, 10], [2, 9], [3, 8], [4, 7]]

Output: 4

The intervals are nested: all four are running during the seconds 4 to 6.

Constraints

1 <= intervals.length <= 10^5
0 <= start < end <= 10^9

#intervals
#sweep-line
#sorting
#two-pointers