Meetings run from their start time up to (but not including) their end time, so a meeting ending at 10 and one starting at 10 can share a room. What is the smallest number of rooms that fits them all?
Input
The first line has n (1 ≤ n ≤ 10⁵). Each of the next n lines has start end (start < end).
Output
The number of rooms.
Examples
Example 1 · Input
3 0 30 5 10 15 20
Expected output
2
Example 2 · Input
2 7 10 2 4
Expected output
1
Prompts inside input() are ignored when checking, so input("n: ") is fine.
Hints
Hint 1
Turn each meeting into two events: a start (+1 room) and an end (−1 room).
Hint 2
Sort the events by time; at equal times, ends come before starts, so a room is freed before it is reused.
Hint 3
The answer is the largest running total.
Solution
Show one correct solution (try it yourself first)
n = int(input())
events = []
for _ in range(n):
start, end = map(int, input().split())
events.append((start, 1))
events.append((end, -1))
events.sort() # at equal times, (t, -1) sorts before (t, 1)
rooms = best = 0
for _, change in events:
rooms += change
best = max(best, rooms)
print(best)