题目56:intervals[i] = [starti, endi] 。请你合并所有重叠的区间,并返回一个不重叠的区间数组,该数组需恰好覆盖输入中的所有区间 。
思路:先把区间按照起点排序。因为后面我们判断是否应该开启一个新区间,用的判断语句是 if interval[0] > end,只要后一个区间起点比现在区间的终点大,那后面所有区间的起点就都比现在终点大。因此必然不会和现在区间重叠。
题目57:无重叠的intervals,intervals[i] = [starti, endi]。给定一个区间newInterval = [start, end]。在intervals 中插入区间newInterval,使得intervals按照starti升序排列,且区间之间不重叠(如果有必要的话,可以合并区间)。
思路:添加新区间到intervals,然后按照起点排序。之后就是合并区间的逻辑了。
题目435:intervals[i] = [starti, endi]。返回 需要移除区间的最小数量,使剩余区间互不重叠 。
思路:先按照终点排序。原因是我们判断的逻辑是 if intervals[i][0] < end,如果新区间起点比现在的终点还大,说明这个区间太大了(排序已经保证了后续区间的终点大过现有区间的终点)。那新区间就该删除。
题目452:整数数组points为气球的大小,points[i] = [xstart, xend]表示直径在xstart和xend之间的气球。在坐标 x 处射出一支箭,若有一个气球的坐标满足xstart≤ x ≤ xend,则该气球会被 引爆。返回引爆所有气球所必须射出的 最小 弓箭数。
思路:先按照终点排序。原因是我们射一支新的箭的逻辑是,沿着第一个区间的终点射出。如果后续气球的起点小于箭头高度,终点一定大于箭头高度(因为按照终点排序,后续区间的终点一定大于当前终点,也就是箭头),必然会被射中。反之,如果气球的起点大于箭头高度,那需要新射出一支箭。