Non-overlapping Intervals

Moderate
0/80
Average time to solve is 27m
profile
Contributed by
36 upvotes
Asked in companies
FacebookOracleAmazon

Problem statement

Ninja is the steel factory owner, and there are 'N' workers working at that factory. Each worker has his own working time, and it is provided in the array 'intervals' where 'INTERVALS[i][0]' gives the start time of the 'i'th worker and 'INTERVALS[i][1]' gives the end time of the 'i'th worker.

Ninja does not want to allow more than one worker to work at the same time, so he needs your help to find the minimum number of workers he needs to reschedule their work time so as there are non-overlapping working times in any two workers.

Example: 
Input: 'INTERVALS' = [[1, 2], [1, 3], [2, 3], [3, 4]]
Output: 1

After rescheduling the worker with the interval [1, 3] it is possible to get the non-overlapping working times.
Detailed explanation ( Input/output format, Notes, Images )
Input Format : 
The first line of input contains an integer 'T', denoting the number of test cases. 

The first line contains an integer 'N' size of the list 'intervals' next 'N' lines will contain two integers, each start and end time for each worker.
Output format : 
For each test case, print the minimum number of workers needed to reschedule their work time so as there are non-overlapping working times in any two workers.

Output for each test case will be printed in a separate line.
Note : 
You don't need to print anything. It has already been taken care of. Just implement the given function.
Constraints : 
1 <= ‘T’ <= 10
1 <= 'N' <= 10^4
'INTERVALS[i].LENGTH' == 2
'INTERVALS[i][0]' < 'INTERVALS[i][1]'
'INTERVALS[i][j]' <= 10^9
Time Limit: 1sec
Sample Input 1 :
2
4
1 2
2 3
1 3
3 4
3
3 4
4 5
5 6
Sample Output 1 :
1
0
Explanation Of Sample Input 1 :
For the first test case, After rescheduling the worker with the interval [1, 3] it is possible to get the non-overlapping working times.

For the second test case, there are no overlapping time intervals. Hence we do not need to reschedule any worker's time.
Sample Input 2 :
2
5
2 3
4 5
6 7
2 4
3 6
4
4 6
4 7
3 5
3 5
Sample Output 2 :
2
3
Hint

Can you approach according to the ending point of each interval?

Approaches (1)
Greedy Solution

Approach:  For this problem, we just want to eliminate some intervals so there are no overlapping intervals after that.

 

We can easily achieve this by sorting the intervals by their ending position and then greedily incrementing the counter according to the number of overlaps.

 

Algorithm : 

  1. Initialize the variable 'answer' with -1.
  2. Declare the comparator 'compare' with input parameters 'vector<int> a', 'vector<int> b' and return 'a[1]' < 'b[1]' in it.
  3. Sort the 'intervals' with the custom comparator 'compare'.
  4. Initialize the vector 'previous' with 'intervals[0]'.
  5. Iterate over the array 'intervals' with iterator 'i'.
    • If 'previous[1]' > 'i[0]' then increment the 'answer' by 1.
    • Else update 'previous' by 'i'.
  6. Return 'answer'.
Time Complexity

O(N * LogN), Where 'N' is the size of the input array 'INTERVALS'.

 

As we are sorting the array of size 'N' and then iterating over time, complexity will be O(N* LogN).

Space Complexity

O(1)

 

As we are using the constant extra space, the space complexity will be O(1).

Video Solution
Unlock at level 3
(75% EXP penalty)
Code Solution
(100% EXP penalty)
Non-overlapping Intervals
Full screen
Console