Non-overlapping Intervals

Moderate

0/80

Average time to solve is 27m

Contributed by

32 upvotes

Asked in companies

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 :

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 :

Sample Output 2 :

2
3

Console