Meetings II
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

Question

Meetings II

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

Accepted Answer

The task is to find the minimum number of conference rooms required to organize all the meetings.

Sort the meetings based on their start time.
Initialize a priority queue to store the end times of the meetings in ascending order.
Iterate through the sorted meetings and check if the start time of the current meeting is greater than the end time of the meeting at the top of the priority queue.
If it is, remove the meeting from the priority queue.
Add the end time of the current meeting to the priority queue.
The size of the priority queue at any point will give the minimum number of conference rooms required.

Accepted Answer

Brute Force

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
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
Else decrement the count of ROOMREQUIRED by 1 and increment j by 1.

Return RESULT.

Space Complexity: O(1)Explanation:

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

Time Complexity: O(1)Explanation:

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

Accepted Answer

Heaps

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

Space Complexity: O(1)Explanation:

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

Because we’ll be creating a heap in memory.

Time Complexity: O(1)Explanation:

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

Because we’ll be sorting the array and also we’ll be inserting elements into the heap.

Accepted Answer

EfficientApproach

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

Space Complexity: O(1)Explanation:

O(1).

We are using constant extra memory.

Time Complexity: O(1)Explanation:

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

Because we’ll be iterating through the array once.

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:

Note:

For Example:

Input format

Output Format

Note:

Constraints:

Top Texas Instruments Software Developer Intern interview questions & answers

Popular interview questions of Software Developer Intern