面试刷题：移除被覆盖的区间
By 青衣极客 Blue Geek In 2020-03-31
在使用C++的STL中的某些算法时，我们常常需要定制一些函数，以保证算法是执行在我们选定的数据上的。 对于简单的情况，可以直接提供一个函数；对于复杂的情况，compare本身需要依赖一些资源，简单函数无法完成，则只能使用仿函数(Functor)。 简单函数的情况极为直观，不值得专门演示，这里主要是借用Q1288这道题讲述一下仿函数的写法。
1. 题目
给定一列区间 intervals，移除其中可以被任何其他区间覆盖的区间。
定义区间(a,b)能被区间(c,d)覆盖，只在c<=a并且d>=b条件下成立。
任务完成之后返回剩余区间的个数。
约束条件：
(a) 1 <= intervals.length <= 1000
(b) 0 <= intervals[i][0] < intervals[i][1] <= 10^5
(c) intervals[i] != intervals[j] for all i != j
示例1:
Input: intervals = [[1,4],[3,6],[2,8]]
Output: 2
解释：
[3,6]区间被[2,8]区间覆盖，所以被移除了。
2. 思路一
对于这种compare类型的问题，我们都可以采用暴力枚举的方法来解决。
比如这道题，我们可以使用两层循环，逐个来进行compare，移除被覆盖的区间，剩下的就是答案了。
这种思路的算法时间复杂度为O(n^2)，说不上是个好方法，但如果没有更好的方法也可以先用上。
3. 思路二
所幸我们其实还很容易想到一个更好的方法：先排序，再比较。 可以使用一下的伪代码来描述这种算法：
Input: intervals, n x 2, int
Initialize: ret = 0
-----------------
S1: intervals = sort_ascending(intervals, key_idx=0)
S2: i->intervals[0], j->intervals[1]
S3: if is_covered(i, j) then
remove(j), j = next(j)
S4: if not is_covered(i, j) then
i = j
j = next(j)
ret = ret + 1
S5: goto S3 until any of i,j is invalid
-----------------
Output: ret, number of reserved intervals
我们已知常用的排序算法最快时间复杂度是nlog(n)，而排序之后再进行的compare操作时间复杂度为O(n)，
因此总体来看，这种思路的时间复杂度为nlog(n)，比“思路一”的暴力枚举要更优一点。
基于C++语言实现的思路二代码如下：
// build a functor
class Comp {
public:
bool operator()(vector<int> & a, vector<int> & b) {
return a[0] < b[0];
}
};
class Solution {
public:
// 24ms, faster than 75.58%
int removeCoveredIntervals(vector<vector<int>>& intervals) {
// sort intervals by the first coordinate
Comp comp;
sort(intervals.begin(), intervals.end(), comp);
// count intervals
int len = intervals.size();
int cnt = 1; // counter the first interval
for (int i=0, j=1; i<len && j<len; ++j) {
// meet the one cannot be covered
if (intervals[i][1] < intervals[j][1]) {
i = j;
++cnt;
}
}
return cnt;
}
};
这段程序中最关键的一步就是根据区间的起点坐标进行排序。 STL的algorism中由一个sort函数，该函数实现了快速排序，是我们常用的一种排序方法。 sort函数由一个默认的比较函数，在本题中，默认的compare方法不能用。 我们需要自定义一个compare函数，该函数的输入是两个区间，然后compare区间起始坐标的大小。
以上的实现代码中，定义了一个类，然后重载了这个类的()操作符，这样该类的对象就可以像函数一样被调用了，也就是“仿函数”。
通常我们使用这种方式来持有一些在compare时需要用到的资源。
比如，如果compare需要依赖于查询词典，我们可以将词典的指针传给构造函数，然后利用一个成员变量记录下这个词典指针，就可以在对象的成员函数中使用了。这个小技巧无论是在Leetcode刷题中，还是在工作开发中，都是比较常用的一种方式。
COMMENT
博客评论区功能由Github Issue提供，提交Issue时请以本文标题为话题。
"BG73-面试刷题：移除被覆盖的区间 Q1288"