Leetcode: Remove Covered Intervals

Given a list of intervals, remove all intervals that are covered by another interval in the list, and return the remaining intervals. Interval [a, b) is covered by interval [c, d) if and ONLY if c <= a and b <= d. Here are the examples:

For one, the intervals input is [[1, 4], [3, 6], [2, 8]] and the output is 2 because [3, 6] is covered by the interval [2, 8]. 

[[1, 4], [2, 3]] results in an output of 1 because 2 is greater than 1 and 4 is less than 3. 

So how are we going to be able to see these intervals.

[1,2] [1,4] [3,4] has answer 1 because all other categories are covered by [1, 4]. 

How do we solve this issue? We will use a greedy algorithm.

However, we need to sort by the end point as well, otherwise we won't know exactly which interval will cover each other. 

The first thing is we have to sort the data, and we will sort this using the heap data structure. The idea to sort the inervals by the start point is pretty obvious, since sorting ensures that start1 < start2. The intervales won't cover one another if end1 < end2 but if end1 >= end2, this means that the interval is covered. Here is an example of the sorting [1, 4] [2,3] [2,5]:

So the intuition is finally covered. 

Now onto the algorithm design:

We want to sort the start point in ascending order and put a longer start point to be the first if 2 intervals have the same start port. We initiate the number of non-covered intervals. We increase the number of non-covered interval if the current interval is not covered by the previous one or end > prev_end, otherwise, the interval is covered, and do nothing. We return this incremented value. This utilizes an Arrays.sort() method. 

Here's the solution with commentary:

 

class Solution {

    public int removeCoveredIntervals(int[][] intervals) {

        //sort by beginning of interval first, then end using the comparator operation.

        Arrays.sort(intervals, new Comparator<int[]>() {

        @Override

         public int compare (int[] o1, int[] o2) {

                return o1[0] == o2[0] ? o2[1] - o1[1] : o1[0] - o2[0]; 

         }

        });

        int count = 0;

        //indicate the end and the previous end sign

        int end = 0, prev_end = 0;

               for(int[] curr : intervals) {

                //see if the end extends the end of the previous interval

                end = curr[1];

                if(prev_end < end) {

                    ++count;

                    prev_end = end;

                }

        }

        return count;

    }

}