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.

• https://leetcode.com/problems/remove-covered-intervals/

Solution

• submit code

class Solution:
    def removeCoveredIntervals(self, intervals: List[List[int]]) -> int:
        ret = 0
        # 按照起点升序排列
        intervals.sort(key=self.takeFirst)
        # 起点相同时降序排列
        for x in range(1,len(intervals)):
            if intervals[x][1] > intervals[x - 1][1] and intervals[x][0] == intervals[x - 1][0]:
                intervals[x][1],intervals[x - 1][1] = intervals[x - 1][1], intervals[x][1]

        left = intervals[0][0]
        right = intervals[0][1]

        for i in range(1, len(intervals)):
            # 覆盖区间
            if intervals[i][0] >= left and intervals[i][1] <= right:
                ret += 1
            # 相交区间，合并
            elif intervals[i][0] <= right and right <= intervals[i][1]:
                right = intervals[i][1]
            # 不相交的情况
            elif right < intervals[i][0]:
                left = intervals[i][0]
                right = intervals[i][1]
        return len(intervals) - ret

    def takeFirst(self, elem):
        return elem[0]

• full code

class Solution3:
    def removeCoveredIntervals(self, intervals):
        ret = 0
        # 按照起点升序排列
        intervals.sort(key=self.takeFirst)
        # 起点相同时降序排列
        for x in range(1,len(intervals)):
            if intervals[x][1] > intervals[x - 1][1] and intervals[x][0] == intervals[x - 1][0]:
                intervals[x][1],intervals[x - 1][1] = intervals[x - 1][1], intervals[x][1]

        print(intervals)

        left = intervals[0][0]
        right = intervals[0][1]

        for i in range(1,len(intervals)):
            print(i,left,right,intervals[i][0],intervals[i][1])
            # 覆盖区间
            if left <= intervals[i][0]  and intervals[i][1] <= right:
                ret += 1
                print("Y")
            # 相交区间，合并
            elif intervals[i][0] <= right and right <= intervals[i][1]:
                right = intervals[i][1]
            # 不相交的情况
            elif right < intervals[i][0]:
                left = intervals[i][0]
                right = intervals[i][1]
        print("ret:",ret)
        return len(intervals) - ret

    def takeFirst(self, elem):
        return elem[0]

S3 = Solution3()
# print(S3.removeCoveredIntervals([[1,4],[3,6],[2,8]]))
print(S3.removeCoveredIntervals([[1,2],[1,4],[3,4]]))