leetcode 1288. 删除被覆盖区间 中等

给你一个区间列表请你删除列表中被其他区间所覆盖的区间。只有当c a且b d时我们才认为区间[a,b)被区间[c,d)覆盖。在完成所有删除操作后请你返回列表中剩余区间的数目。示例输入intervals [[1,4],[3,6],[2,8]]输出2解释区间 [3,6] 被区间 [2,8] 覆盖所以它被删除了。提示​​​​​​1 intervals.length 10000 intervals[i][0] intervals[i][1] 10^5对于所有的i ! jintervals[i] ! intervals[j]分析题目说的覆盖是指任意两个区间是否存在完全覆盖不是多个区间组成的区域覆盖。因此可以对所有区间先按照左端点从小到大排序左端点相同则按照右端点从大到小排序。排好序后设置两个指针一个指针 j 指向作为基准的区间一个指针 i 指向需要检查是否被覆盖的区间。如果 i 会被 j 覆盖则 ans 增加 1如果 i 不会被覆盖则 j 变成 i。检查完所有区间返回 intervals.length - ans 即可。class Solution { public: static bool cmp(const vectorinta, const vectorintb) { if(a[0]!b[0])return a[0]b[0]; return a[1]b[1]; } int removeCoveredIntervals(vectorvectorint intervals) { int nintervals.size(),ans0; sort(intervals.begin(),intervals.end(),cmp); for(int i1,j0;in;i) { if(intervals[i][0]intervals[j][0]intervals[i][1]intervals[j][1]) ans; else ji; } return n-ans; } };