Final: How Many Rooms?

Lab Python Advanced 30 points

Read n meetings with start and end times. Print the smallest number of rooms needed so that no two overlapping meetings share a room (a meeting can start in a room right when another ends). Sort by start time and keep a min-heap of end times of meetings in progress.

Input

Line 1: n. Then n lines start end.

Output

One number.

Example

Input

Output

Sample input available Sample output available

Editor

Python

Hints

Sort meetings by start time.

Before adding a meeting, pop every end time that is ≤ its start (those rooms are free).

The biggest heap size ever seen is the answer.

Solution explanation

The heap holds the end times of meetings happening right now; its size is the number of busy rooms.

Show solution

import heapq
n = int(input())
meetings = sorted(tuple(map(int, input().split())) for _ in range(n))
ends = []
rooms = 0
for s, e in meetings:
    while ends and ends[0] <= s:
        heapq.heappop(ends)
    heapq.heappush(ends, e)
    rooms = max(rooms, len(ends))
print(rooms)

Output

Answer