Last Updated: 13 Feb, 2021
Find Conflicting Meetings
Easy
Asked in companies
Mr. X is a busy person. He has to attend 'N' meetings throughout the day. You are given the schedule of Mr. X in a 2D Matrix 'MEETINGS' having 'N' rows and 2 columns. The 'i'th element of the first column contains the starting time of the 'i'th meeting, and the 'i'th element of the second column contains the ending time of the 'i'th meeting.
Two meetings are conflicting with each other if they overlap each other for some non-zero time. If a meeting 'X' starts at the same time as the meeting 'Y' ends, then they do not conflict.
Given the schedule of the day of Mr. X. Find the index of any one conflicting meeting for each of the 'N' meetings.
In case a particular meeting does not conflict with any meeting, take -1 as the index of the conflicting meeting for that meeting.
Note :
If there are multiple conflicting meetings for a particular meeting. You can return any one of them.
Example :
Consider the matrix MEETINGS = [ [ 1, 3 ] , [ 4, 5 ] , [ 2, 5 ] ]
The array containing the Conflicting Meetings will be [ 3, 3, 1 ].
Input Format :
The first line of the input contains an integer 'T,’ denoting the number of test cases.
The first line of each test case contains an integer 'N', denoting the number of meetings.
The second line of each test case contains 'N' space-separated integers denoting the first column of the matrix 'MEETINGS'.
The third line of each test case contains 'N' space-separated integers denoting the second column of the matrix 'MEETINGS'.
Output Format:
For each test case, return the array of conflicting meetings.
The output is '1' if the returned conflicting meetings array is correct, otherwise, it will print '0'.
Note :
You do not need to print anything, it has already been taken care of. Just implement the given function.
Constraints :
1 <= T <= 10
1 <= N <= 10^4
1 <= MEETING[i][0] < 10^9
MEETING[i][0] < MEETING[i][1] <= 10^9
Time Limit : 1 sec
Approaches
The idea is to find the Conflicting Meeting for each meeting one by one. To find a Conflicting Meeting for any particular meeting, we will iterate through each meeting and check whether the two meetings overlap. If we reach the end of the matrix without finding any conflicting meeting, then we will set the index of the conflicting meeting as -1 for that element.
Here is the algorithm :
- Create an array (say, ‘ANS’) that stores the index of conflicting meetings for each meeting.
- Run a loop from 0 to ‘N’ - 1 (say, iterator ‘i’)
- Update ‘ANS’[i] as -1.
- Run a loop from 0 to ‘N’ - 1 (say, iterator ‘j’)
- If the 'i'th meeting overlaps with the 'j'th meeting, then update ‘ANS’[i] as ‘j’ + 1 and break the loop. We are using ‘j’ + 1 here instead of ‘j’ because the meetings need to be 1-indexed.
- To check whether the 'i'th meeting overlaps with the 'j'th meeting. We need to ensure that the meetings ‘i’ and ‘j’ are different ( ‘i’ should not be equal to ‘j’ ), and the minimum value among the end times of both the meetings should be strictly greater than the maximum value among the start times of both the meetings. If both the conditions are true for any two meetings, then they will overlap. Otherwise, they will not overlap.
- If the 'i'th meeting overlaps with the 'j'th meeting, then update ‘ANS’[i] as ‘j’ + 1 and break the loop. We are using ‘j’ + 1 here instead of ‘j’ because the meetings need to be 1-indexed.
- Finally, return the ‘ANS’ array.
The idea is to sort the meeting intervals in ascending order based on the starting time. Then we will iterate through that sorted array, and for every element, we will need to check only the meeting which has the highest end time among all the meetings that have been traversed earlier. This can be done efficiently by storing the index of the meeting with the highest ending time and the highest ending time while iterating through the array and updating them whenever we find a meeting that has an ending time which is greatest among all the meetings traversed. While traversing the sorted array, whenever we will find two conflicting meetings, we will update the output array for both of the conflicting meetings.
Here is the algorithm :
- Create an array (say, ‘sortedMeetings’) that we will use to store the meetings in sorted order.
- Run a loop from 0 to ‘N’ - 1 (say, iterator ‘i')
- Add the tuple [ 'MEETINGS'[i][0], ‘MEETINGS’[i][1], ‘i’ + 1 ] to the ‘sortedMeetings’ array.
- Sort the ‘sortedMeetings’ array based on the starting time in ascending order.
- Create two variables (say, ‘highestEndTime’ and ‘INDEX’ )to store the latest ending meeting and its corresponding index respectively. Set ‘highestEndTime’ as ‘sortedMeetings’[0][0] and ‘index’ as ‘sortedMeeting’[0][2].
- Create an array (say, ‘ANS’) that will be the output array. Set all elements of the array as -1.
- Run a loop from 1 to ‘N’ - 1 (say, iterator ‘i’)
- If ‘highestEndTime’ is greater than ‘sortedMeetings’[i][0], then update ‘ANS’[sortedMeeting[i][2]-1] as new INDEX and update ‘ANS’[INDEX-1] as ‘sortedMeeting’[i][2]. Here, we are checking whether the meeting at the 'i'th position in the ‘sortedMeeting’ array conflicts with the meeting 'INDEX' i.e., the meeting having the highest end time.
- If ‘highstEndTime' is smaller than ‘sortedMeetings’[i][1], then update ‘highestEndTime’ to ‘sortedMeetings’[i][1], and update 'INDEX' to ‘sortedMeetings’[i][2].
- Finally, return the ‘ANS’ array.