一个方法解决三道区间问题 :: labuladong的算法小抄

[utterances-bot]

文章链接点这里：一个方法解决三道区间问题

评论礼仪 见这里，违者直接拉黑。

[jemmy512]

1288 感觉可以再简化一下，排好序后：当i < j, interval[j][0] >= interval[i][0] 这一定成立，所以只要interval[i][1] < interval[j][1], interval[i]一定不覆盖interval[j]

// C++ solution
class Solution {
public:
    int removeCoveredIntervals(vector<vector<int>>& intervals) {
        sort(intervals.begin(), intervals.end(), [](const auto& lhs, const auto& rhs) {
            return lhs[0] != rhs[0] ? lhs[0] < rhs[0] : lhs[1] > rhs[1];
        });

        int end = 0;
        int covered = 0;

        for (const auto& inter : intervals) {
            if (end < inter[1]) {
                ++covered;
                end = inter[1];
            }
        }

        return covered;
    }
};

[lumaster]

1288 排序后可以直接套单调栈模板，返回 stack.size() 就是答案。

[zzp-seeker]

起点升序排序，终点降序 然后只需要判断覆盖情况即可

class Solution:
    def removeCoveredIntervals(self, s: List[List[int]]) -> int:
        n = len(s)
        s = sorted(s,key=lambda k:(k[0],-k[1]))
        a = s[0]
        res = 0
        for i in range(1,n):
            b = s[i]
            if b[1]<=a[1]:
                res += 1
            else:
                a = b
        return n-res

[g-yit]

由于left是单调递增的，所以只需要判断和更改right就可以了

class Solution {
    public int removeCoveredIntervals(int[][] intervals) {
        Arrays.sort(intervals, new Comparator<int[]>() {
            @Override
            public int compare(int[] o1, int[] o2) {
                if (o1[0] == o2[0]) {
                    return o2[1] - o1[1];
                }
                return o1[0] - o2[0];
            }
        });
        int right = intervals[0][1];
        int count = 0;
        for (int i = 1; i < intervals.length; i++) {
            //重合 由于left是递增的所以只用判断intervals[i][1] <= right即可，也不需要left变量
            if (intervals[i][1] <= right) {
                count++;
            } else {
                right = intervals[i][1];
            }
        }
        return intervals.length - count;
    }
}

[hwhaocool]

不去维护和使用 left，这样逻辑上反而好理解一些

[Yijia0106]

终于发现东哥审题的疏漏了？

class Solution {
    public int removeCoveredIntervals(int[][] intervals) {
        Arrays.sort(intervals,(a,b)->{
            if(a[0]==b[0]) return b[1]-a[1];
            else return a[0]-b[0];
        });
        int left = intervals[0][0];
        int right = intervals[0][1];
        int res=intervals.length;
        for(int i=1;i<intervals.length;i++){
            int[] cur = intervals[i];
            if(cur[1]<=right){
                res--;
                continue;
            }
            left = cur[0];
            right = cur[1];

            
        }
        return res;
    }
}

[Maxiah]

感觉课程里的文章好像比我之前看过的简略了很多，是修改了吗？

[YEthYuan]

56题java版代码：

class Solution {
    public int[][] merge(int[][] intervals) {
        int n = intervals.length;
        LinkedList<int[]> res = new LinkedList<>();
        Arrays.sort(intervals, (a, b) -> {
            if(a[0]!=b[0]) return a[0]-b[0];
            else return b[1]-a[1];
        });
        res.add(intervals[0]);
        for(int i=1;i<n;i++){
            int[] last = res.getLast();
            int[] curr = intervals[i];
            if(curr[1]<=last[1]) continue;
            if(curr[0]<=last[1]) {
                last[1] = Math.max(curr[1], last[1]);
                res.removeLast();
                res.add(last);
            } else{
                res.add(curr);
            }
        }
        int[][] r = new int[res.size()][2];
        for(int i=0;i<res.size();i++){
            r[i][0]=res.get(i)[0];
            r[i][1]=res.get(i)[1];
        }
        return r;
    }
}