由于本题只要求 “需要移除区间的最小数量”,所以不需要模拟区间被删除的过程。同时本题如果要直接统计重叠区间也不是很方便,我们将问题转化为先求这些区间中非重叠的区间,再用区间总数减去非重叠区间的个数得到答案。
首先将这些区间按右边界从小到大排序,从左向右遍历 intervals 记录非重叠区间的个数。按右边界排序后,默认第一个区间 [a b] 为非重叠区间,之后往后寻找第一个满足 b <= c 条件的区间 [c d] 作为第二个非重叠区间,再往后寻找第一个满足 d <= e 的区间 [e f] 作为第三个非重叠区间……以此类推直到遍历完所有 intervals。之后将区间总个数减去非重叠区间个数即为要去除的重叠区间个数。
本题也可以用 #452 的思路解决,因为箭的数量就是非重叠区间的数量。只不过本题中 [1 2] 与 [2 3] 是被视为非重叠区间的,那么我们只需要在 #452 的代码中稍微修改一下即可。
实质上本方法就是将区间按左边界排序后的解法。