Find Conflicting Meetings

Easy
0/40
Average time to solve is 15m
profile
Contributed by
6 upvotes
Asked in companies
AmazonRazorpayWalmart

Problem statement

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 ].
Detailed explanation ( Input/output format, Notes, Images )
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
Sample Input 1 :
2
3
1 2 5
3 4 7
2
1 3 
2 4
Sample Output 1 :
1
1
Explanation For Sample Input 1 :
For the first test case,
The two meetings, Meeting 1 and Meeting 2 overlap with each other. Hence, they are conflicting. Meeting 3 does not overlap with any other meeting. 
Therefore, the output array is : [ 2, 1, -1 ] in this case.

For the second test case,
Both the meetings do not overlap with each other. So, there are no conflicting meetings. 
Therefore, the output array : [ -1, -1 ] in this case.
Sample Input 2 :
2
4
6 2 6 1
7 6 8 4
4
5 6 1 3
6 8 4 5
Sample Output 2 :
1
1
Explanation For Sample Input 2 :
For the first test case,
The two meetings, Meeting 1 and Meeting 3, overlap with each other, and Meeting 2 and Meeting 4 overlap with each other. Therefore, the output array is : [ 3, 4, 1, 2 ] in this case.

For the second test case,
The first two meetings do not conflict with any of the meetings. The two meetings, Meeting 3  and Meeting 4, overlap with each other. Therefore, the output array is : [ -1, -1, 4, 3 ] in this case.
Hint

Try to find out the Conflicting Meeting for each of the meetings by iterating through all the meetings and checking whether the two meetings overlap.

Approaches (2)
Brute Force

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 :

 

  1. Create an array (say, ‘ANS’) that stores the index of conflicting meetings for each meeting.
  2. 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.
  3. Finally, return the ‘ANS’ array.
Time Complexity

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

 

When none of the meetings overlap, it takes O(N) time to find to iterate the matrix ‘MEETINGS’ for each of the ‘N’ meetings. Hence, the overall Time Complexity is O(N^2).

Space Complexity

O(1)

 

We are not using any extra space.Hence, the overall Space Complexity is O(1).

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