435. 无重叠区间

题目链接：435. 无重叠区间

思路：本题与452. 用最少数量的箭引爆气球非常像，弓箭的数量就相当于是非交叉区间的数量，只要把弓箭那道题目代码里射爆气球的判断条件加个等号（认为[0，1][1，2]不是重叠区间），然后用总区间数减去弓箭数量就是要移除的区间数量。

class Solution {public int eraseOverlapIntervals(int[][] intervals) {// 按照区间左边界排序Arrays.sort(intervals, (a,b)-> {return Integer.compare(a[0],b[0]);});int res = 1; // 记录不重叠区间（intervals不为空）for(int i = 1; i < intervals.length; i++) {if (intervals[i][0] >= intervals[i - 1][1]) {res++;}else {// 更新重叠区间最小右边界intervals[i][1] = Math.min(intervals[i][1], intervals[i - 1][1]);}}return intervals.length - res; // 需要移除区间的最小数量}
}

---

763. 划分字母区间

题目链接：763. 划分字母区间

思路：如果找到之前遍历过的所有字母的最远边界，说明这个边界就是分割点。

可以分为如下两步：

• 统计每一个字符最后出现的位置
• 从头遍历字符，并更新字符的最远出现下标，如果找到字符最远出现位置下标和当前下标相等了，则找到了分割点

这道题目leetcode标记为贪心算法，但找不出局部最优推出全局最优的过程。就是用最远出现距离模拟了圈字符的行为。

class Solution {public List<Integer> partitionLabels(String s) {List<Integer> res = new LinkedList<>();int[] hash = new int[26];        char[] ch = s.toCharArray();// 记录每一个字母最后出现的位置。for (int i = 0; i < ch.length; i++) {hash[ch[i] - 'a'] = i;}int cur = 0; // 当前片段出现过的字母的最远边界int last = 0; // 上一个片段结束的下标for (int i = 0; i < ch.length; i++) {// 更新最远边界cur = Math.max(cur, hash[ch[i] - 'a']);if (i == cur) {res.add(cur - last + 1);last = i + 1;}}return res;}
}

---

56. 合并区间

题目链接：56. 合并区间

思路：按照左边界从小到大排序之后，如果 intervals[i][0] <= intervals[i - 1][1] 即intervals[i]的左边界 <= intervals[i - 1]的右边界，则一定有重叠。（本题相邻区间也算重叠，所以是<=）

class Solution {public int[][] merge(int[][] intervals) {LinkedList<int[]> res = new LinkedList<>();// 按区间的 start 升序排列Arrays.sort(intervals, (a, b) -> {return a[0] - b[0];});res.add(intervals[0]);for (int i = 1; i < intervals.length; i++) {int[] cur = intervals[i];// res 中最后一个元素的引用int[] last = res.getLast();if (cur[0] <= last[1]) {// 合并区间，只更新右边界就行last[1] = Math.max(last[1], cur[1]);} else {// 处理下一个待合并区间res.add(cur);}}return res.toArray(new int[res.size()][]);}
}

类似题目：

1288. 删除被覆盖区间 => 覆盖不等同于部分重叠，找到相交区间需要进行合并。

986. 区间列表的交集 => 用 [a1, a2] 和 [b1, b2] 表示在 A 和 B 中的两个区间，如果这两个区间有交集，需满足 b2 >= a1 && a2 >= b1，假设交集区间是 [c1, c2]，那么 c1 = max(a1, b1), c2 = min(a2, b2)。这一点就是寻找交集的核心。

---