合并区间

    技术2026-02-25  16

    3板斧

    先排序:根据左边界排序,相等的话再排右边界。

    前后两个区间,一共3种情况:

    注意合并区间的排序规则;

    在leetcode1288中,要删除被覆盖区间,那么,这个时候排序规则应该是

    先根据左边界排序,对于左边界相同的,有边界倒序。这样如果后面的区间的右边界比前面一个的小,肯定会被覆盖。(因为前面的左边界小于等于后面的左边界)

    我们可以试试如果是按照前面第一种排序方式,会发生什么:

    排序结果应该是 A,B,C.我们把A加入栈,A是B的覆盖区间,A弹出,B进栈,然后C是B的覆盖区间,所以C不进栈。

    这里好像没什么问题。看如果按第二种排序方法呢:

    排序结果是BAC,这样,B进栈,A,C因为被覆盖都不会进栈。‘

    最关键的是这样做可以不用分类,因为按照第二种排序的话,如果覆盖区间,一定是前面的覆盖后面的,而不可能后面的覆盖前面的。

    Processed: 0.012, SQL: 9