贪心：java实现

区间覆盖问题

• 题目链接：https://vjudge.z180.cn/problem/POJ-2376#author=SDUProgramming

import java.util.*;

public class 区间覆盖 {

	public static void main(String[] args) {
		// TODO Auto-generated method stub
		Scanner scan = new Scanner(System.in);
		final int N = scan.nextInt();
		final int S = 1;
		final int T = scan.nextInt();
		int[][] itvs = new int[N][2]; 
		for (int i = 0; i < N; i++) {
			itvs[i][0] = scan.nextInt();
			itvs[i][1] = scan.nextInt();
		}
		Arrays.sort(itvs, new Comparator<int[]>() {
			public int compare(int[] a, int[] b){
				if(a[0] != b[0]) 
					return a[0] - b[0];
				else 
					return b[1] - a[1];
            }
		});
		int res = 0;
		//初始化, 开始时没有覆盖任何区域
		int s = S - 1;
		int t = S - 1;	//已经覆盖到[S, t]
		for (int i = 0; i < N && t < T; i++) {
			if (itvs[i][0] <= s) {
				t = Math.max(t, itvs[i][1]); //延展范围
			} else {
				res++;	//选了上一轮终点最大的一个点
				s = t + 1;
				if (itvs[i][0] <= s) {	//起点没有超出已经覆盖的范围
					t = Math.max(t, itvs[i][1]);
				} else {
					break;
				}	
			}
		}
		if (t >= T) {
			System.out.print(res);
		} else {
			System.out.print(-1);
		}
	}

}

贪心：java实现

原文：https://www.cnblogs.com/SakuraMoon/p/14190629.html