Last Updated: 3 Apr, 2021
NINJA'S INTERVAL
Easy
Asked in companies
Ninja is assigned some task to complete in the given intervals. Each interval has a starting point and ending point and is given in the form of a list. But there is an issue with these intervals as some intervals starting point and ending points lie in some other intervals so ninja has to remove such intervals and wants to know the count of remaining intervals.
So your task is to detect such intervals and return the count of remaining intervals in the list after removing such overlapping intervals.
Example:
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.
Note:
We can take two intervals even when their starting and ending time are same. For eg: [1,3], [3,5] can be taken together.
Input Format:
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.
Output Format:
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.
Note :
You do not need to print anything, it has already been taken care of. Just implement the given function.
Constraints:
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
Approaches
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.
The idea here is to sort the given list on the basis of starting and ending intervals then we can simply compare them in a single loop.
Algorithm:
- So first we sort our list on the basis of starting point in the interval is smaller if both starting points are equal then we will compare them on the basis of the ending point and sort them if the ending points are greater.
- Now we simply count the intervals one by one subsequently and store the count of such intervals in the ‘ans’ variable.
- Now we simply return the ‘ans’ variable as our answer.