Contained Intervals - Csacademy

https://csacademy.com/contest/interview-archive/task/contained-intervals/

You should implement a function that takes as argument an array of $N$ intervals. For each interval $i$ you are given its end points $(l, r)$. We say that an interval $i$ is contained by another interval $j$ if $l_j \leq l_i$ and $r_i \leq r_j$. Return the number of intervals that are contained by at least one other interval.

Desired solution

This problem admits a variety of $O(N\log N)$ solutions. Can you find the simplest one?

Standard input

The template code reads on the first line a single integer $N$.

Each of the next $N$ lines contains two integers $l$ and $r$ representing the end points of an interval.

Standard output

The template calls your function and outputs the result.

Input	Output
5 1 6 4 6 4 10 5 6 1 3	3
2 1 2 1 2	2

https://zhuanlan.zhihu.com/p/26657786

给一组interval，判断有多少个interval是被至少一个别的interval所包含的(包含的定义：a包含b，就是 a.start <= b.start, a.end >= b.end)。

这道题的思路就是，先按照Interval的start升序排序，对于start相同的interval，按照interval的end的降序排序。这样子可以保证在排序后，对于每一个interval，如果它被另一个interval所包含，那么那个包含它的interval一定在它之前。这是排序的结果所造成的。同时因为排序，每一个interval的start一定大于等于之前的所有interval，所以只要之前有任意一个interval的end大于等于这个interval的end，那么就满足了包含的条件。于是我们就只需要在遍历排序过后的数组时，记录下出现过的最大的end，然后和当下的interval的end作比较。唯一需要注意的一点是，如果前后两个interval的start和end完全相等，那么意味着这两个interval同时被对方所包含，在这种情况下，我们不能漏算前一个interval的情况。因此我们每次都还要比较一下每个interval和后一个interval是否相等。来看一下我的代码，值得解释的是，因为对于排序过后的第一个元素，currentmaxR的比较条件必然成立，所以在初始化res的时候要考虑是否初始化成-1来抵消这次误加。

struct Interval {
    int l, r;
};
bool operator==(const Interval& lhs, const Interval& rhs) {
    return (lhs.l == rhs.l) && (lhs.r == rhs.r);
}
bool myfunction (Interval i,Interval j) {
    if(i.l != j.l)  return (i.l < j.l);
    return (i.r > j.r); 
}
int containedIntervals(vector<Interval>& intervals) {
    if(intervals.empty())   return 0;
    sort(intervals.begin(), intervals.end(), myfunction);
    int currentMaxR = 0;
    int res = intervals.size() > 1 && intervals[0] == intervals[1] ? 0 : -1;
    currentMaxR = intervals[0].r;
    int i = 0;
    for(;i < intervals.size()-1; ++i) {
        if(intervals[i] == intervals[i+1] || intervals[i].r <= currentMaxR)  ++res;
        currentMaxR = max(currentMaxR, intervals[i].r);
    }
    if(intervals[i].r <= currentMaxR)   ++res;
    return res;
}