Meetings II

PROBLEM STATEMENT

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.

Sort ARRIVAL and DEPARTURE arrays.
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.
Return RESULT.

Try Problem

Approach 2

Sort INTERVALS in order of their ARRIVALTIME.
Create a MINHEAP and iterate through INTERVALS[i][j] for each 0 <= i <= N and check:
1. If MINHEAP is empty:
  1. Increment RESULT by 1 and add INTERVALS[i][1] to MINHEAP
2. Else
  1. If INTERVALS[i][0] >= topmost element of MINHEAP, remove topmost element from MINHEAP.
  2. Else increment RESULT by 1
  3. Add INTERVALS[i][1] to MINHEAP
Return RESULT

Try Problem

Approach 3

Initialize an integer array ROOMS of size 2361 because a clock goes from 0000 to 2359 only.
Initialize REQUIREDROOMS to 1
Iterate through INTERVALS[i] for each 0<= i < N and:
1. Increment ROOMS[INTERVALS[i][0]] by 1
2. Decrement ROOMS[INTERVALS[i][1]] by 1
Iterate through ROOMS[i] for each 1 <= i < 2361 and:
1. Assign sum of ROOMS[i] and ROOMS[i-1] to ROOMS[i]
2. Assign MIN of REQUIREDROOMS and ROOMS[i] to REQUIREDROOMS.
Return REQUIREDROOMS

Try Problem