day30 贪心算法-burstBallon+nonOverlappingIntervals+partitionLabels

### 8.13 452. Minimum Number of Arrows to Burst Balloons
There are some spherical balloons taped onto a flat wall that represents the XY-plane. The balloons are represented as a 2D integer array points where points`[i] = [xstart, xend] denotes a balloon whose horizontal diameter stretches between xstart and xend. You do not know the exact y-coordinates of the balloons.
Arrows can be shot up directly vertically (in the positive y-direction) from different points along the x-axis. A balloon with xstart and xend is burst by an arrow shot at x if xstart <= x <= xend. There is no limit to the number of arrows that can be shot. A shot arrow keeps traveling up infinitely, bursting any balloons in its path.
Given the array points, return the minimum number of arrows that must be shot to burst all balloons.
https://leetcode.cn/problems/minimum-number-of-arrows-to-burst-balloons/
https://programmercarl.com/0452.%E7%94%A8%E6%9C%80%E5%B0%91%E6%95%B0%E9%87%8F%E7%9A%84%E7%AE%AD%E5%BC%95%E7%88%86%E6%B0%94%E7%90%83.html  
判断不重叠：如果一个气球的左边界大于前一个气球的右边界，则不重叠，需要多一条弓箭。
判断重叠：如果一个气球的左边界小于等于前一个气球的右边界，则重叠。和下一个气球是否重叠如何判断：更新右边界即可。取两个气球的最小右边界。如果下一个气球的左边界没有大于等于此气球更新后的右边界，那么就不重叠。
>[!Tip] `Integer.compare(a[0], b[0]) 和 a[0] - b[0] 的区别：
>
>当你尝试使用 `a[0] - b[0] 来比较 -2147483648（Integer.MIN_VALUE）和 2147483647（Integer.MAX_VALUE）时，会出现整数溢出。具体来说，-2147483648 - 2147483647 会导致溢出，因为 -2147483648 已经是 int 类型能表示的最小值，再减去任何正数都会导致溢出。这种溢出会导致结果变成正数，从而错误地表明 -2147483648 大于 2147483647。
>
>`Integer.compare(a[0], b[0]):
这是一个静态方法，专门用于比较两个整数。它返回一个整数，表示第一个参数与第二个参数的比较结果。如果` a[0] 小于 b[0]，则返回负数；如果 a[0] 等于 b[0]，则返回 0；如果 a[0] 大于 b[0]，则返回正数。这种方法不会因整数溢出而产生错误的结果，因为它直接通过比较来返回结果，不涉及实际的算术运算。

```java
public class burstBalloon {  
    public int findMinArrowShots(int[][] points) {  
        Arrays.sort(points,(a,b) ->  Integer.compare(a[0],b[0]) );  
        //a[0]-b[0]  
        int result = 1;  
        for (int i = 1; i < points.length; i++) {  
            //当前气球的左边界小于等于上一个气球的右边界,则重叠  
            if(points[i][0] <= points[i-1][1]){  
                //将当前气球的右边界更新为当前气球和前一个气球右边界的最小值  
                points[i][1] = Math.min(points[i][1],points[i-1][1]);  
            }else{  
                result++;  
            }  
        }  
        return result;  
    }  
}  
class burstBalloonTest {  
    public static void main(String[] args) {  
        burstBalloon example = new burstBalloon();  
        int[][] point = {  
                //{10,16},{2,8},{1,6},{7,12}  
                //{1,8},{3,4},{5,6},{7,8}                {-2147483646,-2147483645},{2147483646,2147483647}  
        };  
        System.out.println(example.findMinArrowShots(point));  
    }  
}
```
### 8.14 435. Non-overlapping Intervals
Given an array of intervals intervals where intervals`[i] = [starti, endi], return the minimum number of intervals you need to remove to make the rest of the intervals non-overlapping.
https://leetcode.cn/problems/non-overlapping-intervals/description/
https://programmercarl.com/0435.%E6%97%A0%E9%87%8D%E5%8F%A0%E5%8C%BA%E9%97%B4.html  
这和射气球非常像，先写按左边界排序的版本：
```java
public class nonOverlappingIntervals {  
    public int eraseOverlapIntervals(int[][] intervals) {  
        Arrays.sort(intervals,(a,b) -> Integer.compare(a[0],b[0]));  
        int result = 0;  
        for (int i = 1; i < intervals.length; i++) {  
            if(intervals[i][0] < intervals[i-1][1]){  
                result++;  
                intervals[i][1] = Math.min(intervals[i][1],intervals[i-1][1]);  
            }else{  
                continue;  
            }  
        }  
        return result;  
    }  
}  
class nonOverlappingIntervalsTest {  
    public static void main(String[] args) {  
        nonOverlappingIntervals example = new nonOverlappingIntervals();  
        int[][] intervals = {  
                {1,2},{2,3},{3,4},{1,3}  
        };  
        System.out.println(example.eraseOverlapIntervals(intervals));  
    }  
}
```
这也可以按右边界排序。 
```java
//按照右边界排序  
public int eraseOverlapIntervalsRight(int[][] intervals) {  
    Arrays.sort(intervals,(a,b) -> Integer.compare(a[1],b[1]));  
  
    int lapping = 0;  
  
    for (int i = 1; i < intervals.length; i++) {  
        if(intervals[i][0] < intervals[i-1][1]){  
            lapping++;  
            intervals[i][1] = intervals[i-1][1];  
        }else{  
            continue;  
        }  
    }  
    return lapping;  
}
```
### 8.15 763. Partition Labels
You are given a string s. We want to partition the string into as many parts as possible so that each letter appears in at most one part.
Note that the partition is done so that after concatenating all the parts in order, the resultant string should be s.
Return a list of integers representing the size of these parts.
https://leetcode.cn/problems/partition-labels/description/
https://programmercarl.com/0763.%E5%88%92%E5%88%86%E5%AD%97%E6%AF%8D%E5%8C%BA%E9%97%B4.html  
解释：
s = "ababcbacadefegdehijhklij"
第一个字母为a，需要把s中所有的a都包含进来。包含的过程中经过了b c，所以也要把它们都包含进来。
```java
public class partitionLabels {  
    public List<Integer> partitionLabels(String s) {  
        List<Integer> result = new ArrayList<>();  
        int[] hash = new int[27];  
        //统计最远出现第i个字母的index  
        for (int i = 0; i < s.length(); i++) {  
            hash[s.charAt(i)-'a'] = i;  
        }  
        int left = 0;  
        int right = 0;  
        for (int i = 0; i < s.length(); i++) {  
            //不断更新右边界  
            right = Math.max(right,hash[s.charAt(i)-'a']);  
            //遍历到了一组的最右位置  
            if(right == i){  
                result.add(right - left + 1);  
                //左边界从下一组的第一个开始  
                left = i+1;  
            }  
        }  
        return result;  
    }  
}  
class partitionLabelsTest {  
    public static void main(String[] args) {  
        partitionLabels example = new partitionLabels();  
        System.out.println(example.partitionLabels("ababcbacadefegdehijhklij"));  
        System.out.println(example.partitionLabels("eccbbbbdec"));  
        System.out.println(example.partitionLabels("abcdefghijk"));  
        System.out.println(example.partitionLabels(""));  
    }  
}
```