Minimum Number of Conference Rooms

In this problem, you are given a list of meeting time intervals ( [s_i, e_i) ) for ( i=1,2,\dots,n ), where ( s_i ) and ( e_i ) denote the start and end times, respectively. Your task is to determine the minimum number of conference rooms required so that all meetings can take place without any overlap. Note that two meetings can use the same room only if the start time of one is not earlier than the end time of the other.

inputFormat

Input is read from standard input. The first line contains a single integer ( n ), representing the number of meetings. Each of the following ( n ) lines contains two integers ( s_i ) and ( e_i ) separated by a space, representing the start and end time of a meeting.

outputFormat

Output a single integer to standard output, representing the minimum number of conference rooms required.## sample

5
1 4
2 3
3 5
7 10
8 9

2