Medium

Remove Covered Intervals

LAB

Return how many intervals remain after removing intervals covered by another interval.

EXAMPLES

Example 1

Input
{
  "intervals": [
    [
      1,
      4
    ],
    [
      3,
      6
    ],
    [
      2,
      8
    ]
  ]
}

Output
2

FUNCTION SHAPE

intervals: intMatrix→int

SOLUTION NOTE

We need to sort carefully, first by starting time but if there is a tie then take the one with longer end time first. The intuition is we want all covered intervals to appear after the supersetting interval. Ie. [[1,2],[1,4],[3,4]] should be [[1,4],[1,2],[3,4]]

Now, iterating over intervals: if the previous end time >= current end time, this means the current interval is covered by the previous because the current interval start time is >= the previous intervals start time as well. (intervals is sorted) Otherwise, this current interval is not covered by the previous, so we update our count of remaining intervals and update the end time.

Reveal reference solution +

pythonREFERENCE

def removeCoveredIntervals(self, intervals: List[List[int]]) -> int:
    # Sort by start point.
    # If two intervals share the same start point
    # put the longer one to be the first.
    intervals.sort(key=lambda x: (x[0], -x[1]))
    count = 0
    prev_e = 0

    for _, e in intervals:
        # if current interval is not covered by the previous one
        if prev_e < e:
            count += 1
            prev_e = e

    return count

TimeO(n log n)

SpaceO(1)

Open on LeetCode ↗