Remove Covered Intervals🚲

Question

Given an array intervals where intervals[i] = [li, ri] represent the interval [li, ri), remove all intervals that are covered by another interval in the list.

The interval [a, b) is covered by the interval [c, d) if and only if c <= a and b <= d.

Return the number of remaining intervals.

Example 1:

Input: intervals = [[1,4],[3,6],[2,8]]
Output: 2
Explanation: Interval [3,6] is covered by [2,8], therefore it is removed.

Example 2:

Input: intervals = [[1,4],[2,3]]
Output: 1

Constraints:

• 1 <= intervals.length <= 1000
• intervals[i].length == 2
• 0 <= li < ri <= 105
• All the given intervals are unique.

Java Solution

Two different solutions with two different time complexities, but the second solution will have two different versions both using the same algorithm but the one is using the sort function provided by the language and the other one is using merge sort which is written in the code.

O(n²)
In the below code, I’m checking every pair in an array using brute force, so O(n²) for that.

Code

O(sort)
In the below coding snippets im sorting an array by the first value in ascending order if the values are equal, then im sorting them using the right values by descending order, and depending upon the sort complexities same time complexity will be applied for the whole algorithm as well, yes there is a loop also which goes through the whole array at the end, but as per the Big O rule “Drop non-dominate terms” and since sorting will obviously take more then O(n) that’s why im ignoring that second loop.

In the first version i have used Java’s inner sorting function, which i don’t know which sorting technique it is using, but its faster than the merge sort i have written in the second example.

Code

Version 1

Version 2