452.用最少数量的箭引爆气球

贪心算法

重合最多的气球射一箭，就是局部用箭数量最少的，全局的用箭数量就是最少的。

首先对二维数组进行排序，这样就可以让气球更加紧凑。

思路：当前气球是否和上一个气球区间重合，如果不重合，那就count++；如果重合，要去更新重合气球的重合区间最小的右边界。（因为这样就可以叠加重合的气球，直到有不重合的气球出现，就可以射一箭将重合的气球射爆。）

class Solution {public int findMinArrowShots(int[][] points) {Arrays.sort(points,(a,b)->Integer.compare(a[0],b[0]));int count=1;for(int i=1; i<points.length; i++){if(points[i][0]>points[i-1][1]){count++;}else{points[i][1]=Math.min(points[i-1][1],points[i][1]);}}return count;}
}

435.无重叠区间

与上一题一模一样

class Solution {public int eraseOverlapIntervals(int[][] intervals) {Arrays.sort(intervals,(a,b)->a[0]-b[0]);int count=0;for(int i=1; i<intervals.length; i++){if(intervals[i][0]<intervals[i-1][1]){count++;intervals[i][1]=Math.min(intervals[i][1],intervals[i-1][1]);}}return count;}
}

763.划分字母空间

思路：遍历字符数组，找到每个元素出现的最大位置；然后遍历数组，找到所有遍历过的字母最大出现的位置，并且当前在数组的位置等于其元素最大位置，就是边界位置。

class Solution {public List<Integer> partitionLabels(String s) {List<Integer> list=new ArrayList<>();int[] edge=new int[26];char[] chars=s.toCharArray();for(int i=0; i<chars.length; i++){edge[chars[i]-'a']=i;}int idx=0;int last=-1;for(int i=0; i<chars.length; i++){idx=Math.max(idx,edge[chars[i]-'a']);if(i==idx){list.add(i-last);last=i;}}return list;}
}