Max Meetings in a Room

-

 https://workat.tech/problem-solving/practice/max-meetings-in-a-room

Given the start and finish time of n meetings and just one room to conduct them, find the maximum number of meetings that can be accommodated in that room.

The start and end times are given in minutes from 12:00 AM

Example:
Meetings (Start, End): [(3, 29), (50, 93), (88, 92), (54, 67), (50, 87)]
Max possible meetings: 3

Testing

Input Format

The first line contains an integer ‘T’ denoting the number of test cases.

For each test case, the input contains the following lines:

  • The first line contains an integer n denoting the numbers of meetings.
  • The next n lines, each have two space-separated integers- starti and endi denoting the start and end time of each meeting.

Output Format

One line for each test case, with the maximum number of meetings possible.

Sample Input

4
5
3 29
50 93
88 92
54 67
50 87
5
66 77
55 94
73 79
90 97
43 62
7
57 62
36 80
50 94
12 75
62 68
17 49
62 63
5
32 58
39 48
1 44
40 95
34 73

Expected Output

3
3
3
1

Constraints

1 <= t <= 10
1 <= n <= 5*104
1 <= starti < endi <= 106

---