Maximum meetings
You are given the schedule of N meetings with their start time Start[i] and end time End[i]. But you have only 1 meeting room. So, you need to tell the meeting numbers you can organize in the given room, such that the number of meetings organized is maximum.

Note:

The start time of one chosen meeting can’t be equal to the end time of the other chosen meeting. Also for the same end time, a meeting with a smaller index is preferred.

Input format:

The first line contains an integer 'T' denoting the number of test cases or queries to be run. The first line of each test case or query contains a single integers 'N' denoting the number of meetings. The second line of each test case contains N single space-separated integers denoting the start time of N meetings respectively. The third line of each test case contains N single space-separated integers denoting the end time of N meetings respectively.

Output Format:

For each test case, print the meeting numbers (Consider 1 based indexing) you organized in the given room, in the order in which you organized them such that the number of meetings is maximum.

Note:

You do not need to print anything, it has already been taken care of. Just implement the given function.

Constraints:

1

Question

Maximum meetings

You are given the schedule of N meetings with their start time Start[i] and end time End[i]. But you have only 1 meeting room. So, you need to tell the meeting numbers you can organize in the given room, such that the number of meetings organized is maximum.

Note:

The start time of one chosen meeting can’t be equal to the end time of the other chosen meeting. Also for the same end time, a meeting with a smaller index is preferred.

Input format:

The first line contains an integer 'T' denoting the number of test cases or queries to be run. 

The first line of each test case or query contains a single integers 'N' denoting the number of meetings. 

The second line of each test case contains N single space-separated integers denoting the start time of N meetings respectively.

The third line of each test case contains N single space-separated integers denoting the end time of N meetings respectively.

Output Format:

For each test case, print the meeting numbers (Consider 1 based indexing) you organized in the given room, in the order in which you organized them such that the number of meetings is maximum.

Note:

You do not need to print anything, it has already been taken care of. Just implement the given function.

Constraints:

1 <= T <= 5
1 <= N <= 10^5
0 <= Start[i] < End[i] <= 10^9

Time Limit: 1 sec

Accepted Answer

For each test case, print the meeting numbers (Consider 1 based indexing) you organized in the given room, in the order in which you organized them such that the number of meetings is maximum.

Accepted Answer

Using Greedy Approach

The idea is to create a struct array MEETING of size N, where each entry of MEETING will have three elements: meeting number, the start time of the meeting, the end time of the meeting.
Sort the MEETING array in increasing order of end time.
Select the first meeting of the sorted MEETING as your first meeting and add the meeting number in your result vector, also maintain one variable, say currentTime, to maintain the current allotted time. Initialize currentTime with end time of first meeting picked.
Now iterate through the rest of the MEETING array from left to right and for each MEETING[i], check if it is possible to organize that meeting or not. If the start time of the MEETING[i] is greater than the currentTime, means it is possible to organize MEETING[i], add the meeting number of MEETING[i] in your result vector and update currentTime with end time of MEETING[i].
Return the result vector.

Space Complexity: O(n)Explanation:

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

In the worst case, we are creating a MEETING array of size N.

Time Complexity: O(nlogn)Explanation:

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

In the worst case, we are traversing the input arrays once which takes O(N) time and we are sorting the MEETING array of size N which takes O(N * log(N)) time. Thus the final time complexity is O(N) + O(N * log(N)) = O(N * log(N)).

You are given the schedule of N meetings with their start time Start[i] and end time End[i]. But you have only 1 meeting room. So, you need to tell the meeting numbers you can organize in the given room, such that the number of meetings organized is maximum.

Note:

Input format:

Output Format:

Note:

Constraints:

Top Nagarro Software Developer interview questions & answers

Popular interview questions of Software Developer

Top HR questions asked in Nagarro Software Developer