NINJA'S INTERVAL

Let assume the given interval list is ‘[ [ 1, 4 ], [ 5, 10 ], [ 6, 9 ] ] so we return ‘2’ as our answer as the interval [ 6, 9 ] lies in the interval [ 5, 10 ] so we removed [ 6, 9 ] from the list hence remaining intervals left are ‘2’ so ‘2’ is our answer.

The first line of input contains a ‘T’ number of test cases. The first line of each test case contains an integer ‘N’ denoting the size of the given interval list. Then, ‘N’ lines follow. Each line contains two space-separated integers denoting the starting and ending points of the interval.

For each test case, print a single line containing the remaining intervals left in the list after removing intervals that lie in other intervals. The output of each test case will be printed in a separate line.

1 <= T <= 5 1 <= N <= 3000 0 <= arr[i][0], arr[i][1] < 10 ^ 9 Where ‘T’ is the number of test cases, ‘N’ is the size of the given list or we can say an array of array, and ‘arr[i][0]’ and ‘arr[i][1]’ represents the starting and ending points of the intervals. Time Limit: 1 sec

Test Case 1: For the first test case, the list is [ [ 1, 4 ], [ 5, 10 ], [ 6, 9 ] ]. So we can see that interval [ 6, 9 ] lies in the interval [ 5, 10 ] so we will remove that interval. Hence the remaining intervals left are ‘2’ so we return ‘2’ as our answer. Test Case 2: For the second test case, the list is [ [ 1, 10 ], [ 2, 6 ], [ 3, 8 ] ] So we can see that both [ 2, 6 ] and [ 3, 8 ] lie in the interval [ 1, 10 ] so we removed both the intervals hence the remaining interval is [ 1, 10 ] so we return ‘1’ as our answer.

For this test case, the list is [ [ 2, 4 ], [ 3, 4 ], [ 4, 5 ] ] so we can see that both [ 2, 4 ] and [ 3, 4 ] have some common points so we remove any one of the interval. Hence remaining intervals left is [ 1, 5 ] and [2, 4] so we return ‘2’ as our answer.

Brute Approach

The idea here is to use a brute force approach and compare each and every interval if any interval starting point is greater than or equal to any given interval starting interval and less than or equal to its ending interval we have to count that numbers.

Algorithm:

We start traversing our list of intervals and we compare for each and every given interval and initialize a count variable from ‘0’.
Now for each interval, we check if any interval starting point is greater than any interval starting point and is less than that ending point interval; we increase our count by 1.
Now we repeat the same steps for each and every interval.
Now we simply return the numbers of pairs present in the list minus our count variable as our required answer.

Time Complexity

O(N ^ 2), where ‘N’ represents the size of the given array.

As for each index, we are traversing the whole list so we have to run two nested loops which make the complexity O(N ^ 2).

Space Complexity

O(1),

As no extra space is required.

Problem statement

Sample Input 1:

Sample Output 1:

Explanation for sample input 1:

Sample Input 2:

Sample Output 2:

Explanation of sample input 2: