🎮一刀流·区间清理术：排序定乾坤，贪心斩冗余

你是一名区间猎人，猎头公会甩给你一张悬赏令：清理一批“地图上的套娃区间”。

什么叫套娃区间？就是那些被其他区间完全罩住的倒霉蛋——比如 [3,6) 被 [2,8) 包得像俄罗斯套娃里的那个小娃娃，存在的唯一价值，就是被外面的老大哥代表。这种区间在地图里纯属“占着茅坑不拉屎”——明明霸着一组坐标，实际控制面积为零，纯粹浪费数据空间。不清理掉的话，策划又要开喷了：“你们的边界数据比我昨晚吃的麻辣烫还杂乱！”

你的任务很直白：数数清理完还剩多少个“独当一面的有效区间”。注意，不是让你真的一刀一刀删——数组这玩意儿，中间删一个元素，后面的编号全得往前挪一位，复杂度堪比主城开服时玩家挤传送阵。你只需要优雅地统计出“幸存者”的数量，然后把悬赏令拍回公会的桌子上，领赏走人。

但问题来了：你怎么知道哪个区间被当了套娃？暴力两两对比？拿每个区间去和全图所有区间单挑？O(n²) 的复杂度会让你的CPU 会觉得你在羞辱它。

你冷笑一声，从背后抽出一把泛着幽蓝暗光的太刀——排序之刃。刀身上刻着一行附魔铭文：

lambda x: (x[0], -x[1])

这把刀的排序法则简单粗暴：

• 主属性：按左端点升序排——谁左边起步更早，谁站前面。江湖规矩，先到先得。
• 副属性：如果左端点撞车了，按右端点降序排——谁地盘更大、谁罩得更远，谁就当大哥，站C位。

队友从后排探出脑袋：“哥，为啥右端点要降序？升序不是也挺整齐？我这强迫症看得浑身刺挠！”

你手腕一翻，刀锋在空中划出一道银弧，映出你半张冷峻的脸。你淡淡地吐出几个字：

“为了让罩得最远的大哥先出场。大哥站前面，后面那些小弟一旦被大哥的地盘完全包住，我连刀都不用抬，看一眼就知道它是套娃。装逼要装全套，排序也要有兵法——这叫先发制人，后发制于人。”

你拔出排序之刃，刀尖指天，念出一段古老的咒语：

intervals.sort(key=lambda x: (x[0], -x[1]))

一瞬间，整个地图开始剧烈震动。左端点小的区间像被磁铁吸住一样，连滚带爬地挤向队伍前排；左端点撞车的区间们则开始了残酷的内卷——右端点大的冲击 C 位，右端点小的被动回退。

你看着这支被咒语驯服的队伍，嘴角微微上扬：猎人的工作，从列队完毕那一刻起，就已经结束了九成。 剩下的一成，不过是走个过场，收个人头而已。

你提着排序之刃，刀尖拖在石板地面上，迸出呲呲的火星，像一场即将开场的屠杀预告片。你把左手摊开，掌心浮现出一个变量 max_right，初始值为 0——它记录的是你这一路走来，刀锋扫过的最远右疆界。

你迈开步子，从队头走到队尾，每经过一个区间 [a, b)，只问一个问题：

“你的右边界 b，有没有超过我这把刀至今扫过的极限？”

一问一斩，绝无多余动作。

• 情况一：b ≤ max_right 这厮的右边界没有突破前人留下的记录——左边已经被大哥盖住（排序铁律之下，它的左端点不可能比前辈更靠左，顶多打个平手），右边又被大哥的疆域完全碾压——从头到脚，无一处突围。教科书级别的套娃，连挣扎的资格都不配拥有。不计数，下一个。
• 情况二：b > max_right 嚯！这小子的右边界炸出了新高，硬生生把已知疆土撕开一道缺口！哪怕它的左边界还是被某个大哥压制，至少右边这一段是独享的，是旁人够不着的“独家战区”。这不是套娃，这是开拓者，是配得上被计数的高手。你眼中寒光微闪，幸存者计数 +1，同时腕部一转，刀锋向前劈出一道半月弧光——max_right 应声刷新为 b，地图上烙下一道崭新的疆界线。

你就这样从头走到尾，一步不停，一眼不回头看。排序之刃帮你压死了左边界——后来者永远不可能比前辈站得更靠左。max_right 帮你盯死了右边界——只要后辈的右边界没超过前辈的最远记录，必被吞噬。双刃合璧，一刀封喉，套娃无所遁形。

def removeCoveredIntervals(intervals: List[List[int]]) -> int:
    intervals.sort(key=lambda x: (x[0], -x[1]))
    res = 0
    max_right = 0
    for i in range(len(intervals)):
        if max_right < intervals[i][1]:
            res += 1
            max_right = intervals[i][1]
    return res

一套刀法行云流水，遍历 O(n)，叠加上排序咒语的 O(n log n)，总花费让隔壁还在硬莽双重循环的剑圣羞愧到想删号。至于空间？除排序本身，全程只祭出两个变量——res 与 max_right，堪称环保猎人的典范。

队友在语音频道里惊呼：“卧槽这就完了？你这输出是开了倍速挂还是我电脑卡了？”

你扛起排序之刃，刀身上的附魔铭文在暗处微微脉动。那些曾在地图数据里混吃等死的套娃区间，已被从逻辑上彻底抹除——连删除的痕迹都没留下，仿佛它们从一开始就没在这张地图上刷新过。

你头也不回，步入公会大厅的阴影深处，只抛下一句话，冷得像刀锋入鞘的最后一声轻响：

“猎人不打无谓之猎，套娃不配占用 CPU。”

本作品采用 知识共享署名-非商业性使用-禁止演绎 4.0 国际许可协议 进行许可。