贪心问题
原题链接题解代码案例:输入样例:
5
1 2
2 4
5 6
7 8
7 9
输出样例:
3
1、将每个区间按左端点从小到大进行排序
2、如图所示,可分3种情况
情况一:当前区间完全被上一区间覆盖,直接跳过 情况二:将当前区间的右端点更新为上一区间的右端点,达到区间延长的效果 情况三:当前区间的左端点严格大于上一区间的右端点,则表示该区间不能合并,更新区间且count++
import java.util.* ; class Main{ static int N = 100010; static Node[] range = new Node[N]; public static void main(String [] args){ Scanner san = new Scanner(System.in); int n = san.nextInt(); for(int i = 0 ; i < n ;i++){ int st = san.nextInt(); int sd = san.nextInt(); range[i] = new Node(st,sd); } Arrays.sort(range,0,n,(o1,o2) -> o1.l - o2.l) ;//按照左端点排序 int count = 0;//合并区间的数量 int start = Integer.MIN_VALUE; int end = Integer.MIN_VALUE; for(int i = 0 ; i < n ; i++){ if(range[i].l > end ){ count++; start = range[i].l; end = range[i].r; }else{ end = Math.max(end,range[i].r); } } System.out.println(count); } static class Node{ int l ; int r ; public Node(int l , int r ){ this.l = l ; this.r = r ; } } }