贪心算法习题其二【力扣】【算法学习day.19】

前言

###我做这类文档一个重要的目的还是给正在学习的大家提供方向（例如想要掌握基础用法，该刷哪些题？）我的解析也不会做的非常详细，只会提供思路和一些关键点，力扣上的大佬们的题解质量是非常非常高滴！！！

习题

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

题目链接:452. 用最少数量的箭引爆气球 - 力扣（LeetCode）

题面:

基本分析: 可以通过将右边界升序排序来解决问题

代码:

class Solution {public int findMinArrowShots(int[][] points) {int n = points.length;int sum = 0;int count = 0;int flag = 0;Arrays.sort(points, new Comparator<int[]>() {@Overridepublic int compare(int[] o1, int[] o2) {return o1[1]-o2[1];}});int l = 0;while(l<n){if(count==0){count = 1;flag = points[l][1];l++;continue;}if(points[l][0]<=flag&&points[l][1]>=flag){l++;}else{sum++;count=0;}}if(count==1)sum++;return sum;}
}

2.无重叠区间

题目链接:435. 无重叠区间 - 力扣（LeetCode）

题面：

基本分析: 将右边界升序排序，然后找不互相重叠的有多少个即可

代码:

class Solution {public int eraseOverlapIntervals(int[][] intervals) {if (intervals.length == 0) {return 0;}Arrays.sort(intervals,new Comparator<int[]>(){@Overridepublic int compare(int[] o1, int[] o2) {return o1[1]-o2[1];}});int n = intervals.length;int right=intervals[0][1];int ans=1;for (int i = 1; i < n; i++) {if(intervals[i][0]>=right){ans++;right=intervals[i][1];}}return n-ans; }
}