Minimum Meeting Rooms

You are given a list of meetings represented by their start and end times. Your task is to determine the minimum number of meeting rooms required to host all the meetings such that no two meetings occur in the same room at the same time.

Problem Details:

• Each meeting is defined by two integers: its start time and its end time.
• You need to allocate rooms to meetings in such a way that no two meetings overlap in the same room.
• The answer is the minimum number of rooms required to host all the given meetings.

Mathematical Formulation:

Given an array of meeting intervals \( \{(s_1,e_1), (s_2,e_2), \dots , (s_n,e_n)\} \), determine the minimum number \( k \) such that all meetings can be assigned to one of the \( k \) rooms with no overlapping intervals in the same room.

inputFormat

The first line contains an integer \( n \) representing the number of meetings.

Each of the next \( n \) lines contains two space-separated integers representing the start time and end time of a meeting.

Note: Input is read from standard input (stdin).

outputFormat

Output a single integer representing the minimum number of meeting rooms required.

Note: Output should be written to standard output (stdout).

## sample

3
30 75
0 50
60 150

2