1288 Remove Covered Intervals

1288 Remove Covered Intervals#

Problem#

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.

Examples#

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

Constraint#

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

Analysis#

  • sort the intervals based on the start point

  • traverse the intervals, and compare the end point of the previous interval and the current interval

    • if the end point of the previous interval is greater than the end point of the current interval, then the current interval is covered by the previous interval

Solution#

def removeCoveredIntervals(intervals):
    intervals.sort(key=lambda x: x[0])

    count = 0
    interval = intervals[0]
    for i in range(1, len(intervals)):
        # the previous interval covers the current interval
        if intervals[i][1] <= interval[1]:
            count += 1
        # the current interval covers the previous interval
        elif (intervals[i][0] == interval[0] and intervals[i][1] >= interval[1]):
            count += 1
            interval = intervals[i]
        # no covering
        else:
            interval = intervals[i]
    
    return len(intervals) - count


# test
intervals = [[1,4],[3,6],[2,8]]
print(removeCoveredIntervals(intervals))

intervals = [[1,4],[2,3]]
print(removeCoveredIntervals(intervals))

intervals = [[1,2],[1,4],[3,4]]
print(removeCoveredIntervals(intervals))

2
1
1

def removeCoveredIntervals(intervals):
    intervals.sort(key=lambda x: (x[0], -x[1]))

    count = 0
    end = 0
    for i in range(len(intervals)):
        # the previous interval covers the current interval
        if intervals[i][1] <= end:
            count += 1
        # no covering
        else:
            end = intervals[i][1]
    
    return len(intervals) - count

# test
intervals = [[1,4],[3,6],[2,8]]
print(removeCoveredIntervals(intervals))

intervals = [[1,4],[2,3]]
print(removeCoveredIntervals(intervals))

intervals = [[1,2],[1,4],[3,4]]
print(removeCoveredIntervals(intervals))

2
1
1
Contents