Meetings II

Posted: 26 Nov, 2020
Difficulty: Moderate

PROBLEM STATEMENT

Try Problem

Stark Industry is planning to organize Stark Expo, for which various departments have to organize meetings to check their preparations. Since Stark Tower has limited rooms available for the meeting, Tony decided to allot a room to each meeting so that all the meetings are organized in the least possible conference rooms, and a the moment, only one meeting will happen in one room. So, he asked JARVIS to allot each meeting a room and tell the minimum number of conference rooms to be reserved. But, since JARVIS was busy rendering another Iron Man suit model, he asked you to help.

You are given an array of integers ARR of size N x 2, representing the start and end time for N meetings. Your task is to find the minimum number of rooms required to organize all the meetings.

Note:

1. You can assume that all the meetings will happen on the same day.
2. Also, as soon as a meeting gets over if some other meeting is scheduled to start at that moment, they can then be allocated that room.

Note:

Try to solve the problem in linear time complexity.

For Example:

Consider there are three meetings scheduled with timings:
1pm - 4pm
3pm - 5pm
4pm - 6pm

At the start of time, meeting 1 will be allotted room 1, which will be occupied till 4 pm hence for meeting 2 we’ll have to provide another room. At 4 pm, meeting 3 can be organized in room 1 because by that time, meeting 1 would have ended. Hence we’ll require two rooms for holding all three meetings.
Input format
The first line of input contains an integer 'T' representing the number of the test cases. Then the test case follows.

The first line of each test case contains an integer ‘N’ representing the number of meetings scheduled.

The second line of each test case contains N space-separated integers representing the start time for each meeting.

The third line of each test case contains N space-separated integers representing the end time for each meeting.
Output Format
For each test case, print the minimum number of conference rooms required.

The output of each test case should be printed in a separate line.
Note:
You do not need to print anything; it has already been taken care of. Just implement the given function.
Constraints:
1 <= T <= 100
1 <= N <= 1000
0000 <= INTERVAL[start][end] <= 2359

where 'T' is the number of test cases, 'N' is the number of meetings, and 'INTERVAL[start][end]' represents the starting time and ending time of a meeting.
Time limit: 1 second
Approach 1

Create ARRIVAL and DEPARTURE arrays from given array INTERVALS.

  1. Sort ARRIVAL and DEPARTURE arrays.
  2. Traverse ARRIVAL[i] and DEPARTURE[j] for each 0<= i,j <N and check
    1. If ARRIVAL[i] <= DEPARTURE[j] a room is needed for meeting so we
      1. Increment ROOMREQUIRED by 1 and i by 1.
      2. Check if ROOMREQUIRED is more than RESULT. If yes, update RESULT to ROOMREQUIRED
    2. Else decrement the count of ROOMREQUIRED by 1 and increment j by 1.
  3. Return RESULT.
Try Problem