Meetings II

Moderate
0/80
Average time to solve is 10m
profile
Contributed by
23 upvotes
Asked in companies
BNY MellonAmazonIBM

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.
Detailed explanation ( Input/output format, Notes, Images )
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
Sample Input 1:
3
2
0100 0500
0300 0600
3
0100 0300 0400
0400 0500 0600
3
0100 0300 0200
0700 0500 0300
Sample Output 1:
1
2
2
Explanation of Input 1:
(i) Occupancy of rooms - Room 1: (1-3) (5-6)

(ii) Occupancy of rooms - Room 1: (1-4) (4-6) Room 2: (3-5) 

(iii) Occupancy of rooms - Room 1: (2-3) (3-5) Room 2: (1-7)
Sample Input 2:
3
1
0100
1000
5
0100 0500 0300 0400 0600
0300 0800 0500 0800 0950
6
0100 0900 0100 0300 0200 0400
0200 1200 0200 0400 0600 0700
Sample Output 2:
1
3
2
Explanation of Input 2:
(i) Occupancy of rooms - Room 1: (1-10)

(ii) Occupancy of rooms - Room 1: (1-3) (3-5) (5-8) Room 2: (4-8) Room 3: (6-9:50) 

(iii) Occupancy of rooms - Room 1: (1-2) (3-4) (4-7) Room 2: (1-2) (2-6) (9-12)
Hint

Try to think of a solution where meeting scheduled earlier gets a room

Approaches (3)
Brute Force

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.
Time Complexity

O(N logN), where N is the total number of meetings.

Space Complexity

O(N), where N is the total number of meetings.

Code Solution
(100% EXP penalty)
Meetings II
Full screen
Console