HardArraysNot started

Calculate loading bays needed

Each delivery occupies one loading bay from its arrival minute up to, but not including, its departure minute. Read all delivery intervals and print the minimum number of bays needed so no delivery waits. When one delivery departs at the exact minute another arrives, they may use the same bay.

Input

First line N. Next N lines contain arrival and departure minutes, with arrival smaller than departure.

Output

One integer: the maximum number of deliveries present at the same time.

Example 1

Input

Output

Between minutes 35 and 40, three deliveries occupy bays at once.

Constraints

1 <= N <= 100000
0 <= arrival < departure <= 1000000

Hints

Hint 1 of 3

Sort all arrival times and all departure times separately.

Hint 2 of 3

Use two pointers to process whichever event happens next.

Hint 3 of 3

At an equal time, process the departure first because its bay is immediately reusable.

Solution

Show a reference solution and explanation

Python · reference solution

count = int(input())
intervals = [tuple(map(int, input().split())) for _ in range(count)]
arrivals = sorted(start for start, _ in intervals)
departures = sorted(end for _, end in intervals)
i = j = occupied = needed = 0
while i < count:
    if arrivals[i] < departures[j]:
        occupied += 1
        needed = max(needed, occupied)
        i += 1
    else:
        occupied -= 1
        j += 1
print(needed)

JavaScript · reference solution

const count = Number(readline());
const intervals = [];
for (let i = 0; i < count; i++) intervals.push(readline().split(' ').map(Number));
const arrivals = intervals.map(pair => pair[0]).sort((a, b) => a - b);
const departures = intervals.map(pair => pair[1]).sort((a, b) => a - b);
let i = 0, j = 0, occupied = 0, needed = 0;
while (i < count) {
  if (arrivals[i] < departures[j]) {
    occupied++;
    needed = Math.max(needed, occupied);
    i++;
  } else {
    occupied--;
    j++;
  }
}
console.log(needed);

Approach

The two sorted lists form a chronological event stream without building event objects. An arrival increases the occupied count; a departure decreases it. Choosing departure on a tie models half-open intervals, and the highest occupied count is exactly the required number of bays.