LeetCode 435：无重叠区间
（中等）
题目
描述
给定一个区间的集合，找到需要移除区间的最小数量，使剩余区间互不重叠。
注意:
可以认为区间的终点总是大于它的起点。
区间 [1,2] 和 [2,3] 的边界相互“接触”，但没有相互重叠。
示例1
输入: [ [1,2], [2,3], [3,4], [1,3] ]
输出: 1
解释: 移除 [1,3] 后，剩下的区间没有重叠。
示例 2:
输入: [ [1,2], [1,2], [1,2] ]
输出: 2
解释: 你需要移除两个 [1,2] 来使剩下的区间没有重叠。
示例 3:
输入: [ [1,2], [2,3] ]
输出: 0
解释: 你不需要移除任何区间，因为它们已经是无重叠的了。
思路
此题非常类似于 LeetCode 452 用最少数量的箭引爆气球 这道题，都是利用贪心算法，都是根据二维数组中的每个一维数组的两个参考值作为判断，在本题中，这两个参考值就是每个区间的起始坐标与终点坐标，这类题我们可以先确定下一个参考值，然后便可以解决另一个参考值的判断，对于此题，我们先按各一维数组的起始下标，从小到大排序，在遍历所有一维数组区间时，若第 i + 1 个区间的起始下标，小于第 i 个区间的终止下标，那么 i 与 i + 1 区间便重叠了，这时，基于贪心的局部最优思想，同时又因为结果只要求返回删去重叠区间的数量，因此我们可以更新第 i + 1 个区间的终点下标为 i、i + 1 两个区间的终点下标中较小的那个，这样才能更大限度地减少后续区间重叠的可能，从而达到全局最优解，即删去最少的区间。
实现
public class TX13无重叠区间 {
public int eraseOverlapIntervals(int[][] intervals) {
if (intervals == null || intervals.length == 0) {
return -1;
}
int[][] copy = new int[intervals.length][intervals[0].length];
for (int i = 0; i < copy.length; i++) {
copy[i] = Arrays.copyOf(intervals[i], intervals[0].length);
}
sort(copy);
int count = 0;
for (int i = 0; i < copy.length - 1; i++) {
if (copy[i][1] > copy[i + 1][0]) { //有重叠，舍去有边界较大的那个
count++;
//因为已经用不到i+1的左边界了，因此只管其右边界就可以，即更新有边界
copy[i + 1][1] = Math.min(copy[i][1], copy[i + 1][1]);
}
}
return count;
}
public void sort(int[][] a) {
int n = a.length - 1;
QSort(a, 0, n);
}
private void QSort(int[][] a, int low, int high) {
int pivot; // 枢轴的下标，将某个数放在此位置，使得它左边的值都比它小，右边的都比它大
if (low < high) {
pivot = Partition(a, low, high); // 将a[low..high]一分为二，算出枢轴下标pivot
QSort(a, low, pivot - 1); // 对低子表递归排序
QSort(a, pivot + 1, high); // 对高子表递归排序
}
}
// 交换顺序表a中子表的记录，使枢轴记录到为，并返回其位置
private int Partition(int[][] a, int low, int high) {
int pivotkey = a[low][0]; // 用子表的第一个记录作枢轴记录
while (low < high) { // 从表的两端交替向中间扫描
while (low < high && a[high][0] >= pivotkey) {
high--;
}
swap(a, low, high); // 将比枢轴值小的记录交换到低端
while (low < high && a[low][0] <= pivotkey) {
low++;
}
swap(a, low, high); // 将比枢轴值大的记录交换到高端
}
return low; // 最终low == high，所有返回枢轴所在位置
}
/**
* 交换二维数组中的两个一维数组的位置
* @param array
* @param i
* @param j
*/
public void swap(int[][] array, int i, int j) {
int[] tmp = array[i];
array[i] = array[j];
array[j] = tmp;
}
} 
LeetCode 763：划分字母区间
（中等）
题目
描述
字符串 S 由小写字母组成。我们要把这个字符串划分为尽可能多的片段，同一字母最多出现在一个片段中。返回一个表示每个字符串片段的长度的列表。
示例
输入：S = “ababcbacadefegdehijhklij”
输出：[9,7,8]
解释：
划分结果为 “ababcbaca”, “defegde”, “hijhklij”。
每个字母最多出现在一个片段中。
像 “ababcbacadefegde”, “hijhklij” 的划分是错误的，因为划分的片段数较少。
思路
本题需要两次遍历数组，一次用于统计每个字母的最后出现时的下标并记录到 HashMap 对象中，另一次用于找出每个字符串片段的长度的列表并记录到 ArrayList 对象中， 这两次遍历可以分开进行，也可以合并为一次遍历来同时维护，但是如果合并为同一次遍历，那么会有过多的判断与更多相对无效的语句，因此还是建议分成两次来遍历。我们可以先记录出每个字母最后出现时的下标；再在遍历时用一个变量（例如名为 end，存储本批次的最后位置）记录下当前字母最后出现的位置与本批次的最后位置（即 end），这样，若当前下标等于 end 时，那么便是到了这一批次的终点，这一批次由于是从 start 开始的，因此便可以记录到结果中，更新 start 为 i + 1，在进行后续遍历时，也是同样的道理。初次接触这种类型的贪心思想，可能会有一个地方一开始比较迷糊，也就是：
end = Math.max(end, hashMap.get(s.charAt(i)));
，这段语句的作用是选出每次本划分片段的最后一次下标，也就是满足让同一字母最多出现在一个片段中，它是等于上一次的 end 值，与当前字母的最后一次下标中较大的那个，因此如果这个字母在下一段中，那么一定会在上一次循环时就执行了
if (end == i)
里的语句，已经开始了新的一段。可能文字形式不太容易描述这种思想，因此下面放一张我在题解中选到的一张十分形象的图例：
（声明：下图选自 公众号-代码随想录）
实现
public class TX14划分字母区间 {
public List<Integer> partitionLabels(String s) {
List<Integer> list = new ArrayList();
if (s == null || s.length() == 0) {
return list;
}
//hashMap中存储每个字母最后一次出现的下标
HashMap<Character, Integer> hashMap = new HashMap();
for (int i = 0; i < s.length(); i++) {
char c = s.charAt(i);
if (hashMap.get(c) == null) {
hashMap.put(c, i);
} else {
hashMap.put(c, Math.max(i, hashMap.get(c)));
}
}
int start = 0;
int end = 0;
for (int i = 0; i < s.length(); i++) {
end = Math.max(end, hashMap.get(s.charAt(i))); //找到这一批字符出现的最大右边界
if (end == i) {
list.add(end - start + 1);
start = i + 1;
}
}
return list;
}
}