Leetcode 1288 - Remove Covered Intervals

題目

Problem#

題目給你一個由正整數構成的區間，intervals[i] = [li, ri]，如果區間 [a, b) 被 [c, d) 覆蓋，則代表 $c <= a$ 且 $b <= d$
要你回傳刪掉被覆蓋的區間後，剩下區間的個數。

• N = intervals.size()
  • $1 \leq N \leq 1000$
• 區間範圍: $0 \leq l_i \leq r_i \leq 10^5$

想法#

按照左界排序，如果左界相同的話，則右界大的在前、小的在後，如此一來對於每個左界，只要關心右界延伸去哪
每次去比較右界有沒有包含在最大的右界裏頭，如果有就要減 1。

• 時間複雜度: $\mathcal{O}(N\log{N})$
• 空間複雜度: $\mathcal{O}(N)$

AC Code#

Copy

class Solution
{
public:
    int removeCoveredIntervals(vector<vector<int>>& v)
    {
        sort(v.begin(), v.end(), [](auto &lhs, auto &rhs){
            return lhs[0] == rhs[0] ? lhs[1] > rhs[1] : lhs[0] < rhs[0];
        });
 
        // DBG(v);
 
        int ans = v.size();
        int /*ml = INT_MAX,*/ mr = INT_MIN;
        int l, r;
        for(auto &p : v)
        {
            l = p[0], r = p[1];
 
            // printf("l=%d r=%d | ml=%d mr=%d\n", l, r, ml, mr);
 
            if(/*ml != INT_MAX &&*/ mr != INT_MIN)
            {
                if(/*ml <= l &&*/ r <= mr)
                    ans--;
            }
 
            // ml = min(ml, l);
            mr = max(mr, r);
        }
 
        return ans;
    }
};

view raw leetcode/1288.cpp delivered with ❤ by emgithub

賞析#

• 有的作法是用加的

心得#

一開始沒讀題目還以為是要查區間，讀完才發現沒有