// 数轴上有n个闭区间[ai,bi]。取尽量少的点，使得每个区间内都至少有一个点（不同区间内含的点可以是同一个）。
/*
Intervals
You are given n closed, integer intervals [ai, bi] and n integers c1, ..., cn.
Write a program that:
reads the number of intervals, their end points and integers c1, ..., cn from the standard input,
computes the minimal size of a set Z of integers which has at least ci common elements with interval [ai, bi], for each i=1,2,...,n,
writes the answer to the standard output.

Input
The first line of the input contains an integer n (1 <= n <= 50000) -- the number of intervals.
The following n lines describe the intervals. The (i+1)-th line of the input contains three integers ai,
bi and ci separated by single spaces and such that 0 <= ai <= bi <= 50000 and 1 <= ci <= bi - ai+1.

Output
The output contains exactly one integer equal to the minimal size of set Z
sharing at least ci elements with interval [ai, bi], for each i=1,2,...,n.
Sample Input
5
3 7 3
8 10 3
6 8 1
1 3 1
10 11 1
Sample Output
6
 */
//POJ1201

 

思路：
每次先选单个区间最后一个点，这样更容易包含其它区间，取尽量少的点

 1 import java.util.Arrays;
 2 import java.util.Scanner;
 3 
 4 public class Eight_5贪心策略例题_区间选点问题 {
 5     private static class Interval implements Comparable<Interval>{
 6         int s;
 7         int t;
 8         int c;
 9         
10         public Interval(int s, int t, int c) {
11             this.s = s;
12             this.t = t;
13             this.c = c;
14         }
15 
16         @Override
17         public int compareTo(Interval other) {
18             int x = this.t - other.t;
19             if(x == 0)
20                 return this.s - other.s;
21             else
22                 return x;
23         }
24     }
25     
26     /**
27      * 统计axis上s-t区间已经有多少个点被选中
28      */
29     private static int sum(int[] axis, int s, int t){
30         int sum = 0;
31         for(int i = s; i <= t; i++){
32             sum += axis[i];
33         }
34         return sum;
35     }
36     public static void main(String[] args) {
37         Scanner in = new Scanner(System.in);
38         int n = in.nextInt();
39         Interval[] intervals = new Interval[n];
40         for(int i = 0; i < n; i++){
41             intervals[i] = new Interval(in.nextInt(), in.nextInt(), in.nextInt());
42         }
43         Arrays.sort(intervals);    //按区间右端点排序
44         
45         int max = intervals[n-1].t;    //右端最大值
46         int[] axis = new int[max+1];    //标记数轴上的点是否已经被选中
47         //int[] sums = new int[max+1];
48         for(int i = 0; i < n; i++){
49             //1.查阅区间中有多少个点
50             int s = intervals[i].s; //起点
51             int t = intervals[i].t; //终点
52             int cnt = sum(axis, s, t);    //找到这个区间已经选点的数量，sum[t]-sum[s-1];低效率
53                 
54             //2.如果不够，从区间右端开始标记，遇标记过的就跳过
55             intervals[i].c -= cnt; //需要新增的点的数量
56             while(intervals[i].c > 0){
57                 if(axis[t] == 0){ //从区间终点开始选点
58                     axis[t] = 1;
59                     intervals[i].c--;    //进一步减少需要新增的数量
60                     t--;
61                 }else{    //如果这个点已经被选过了
62                     t--;
63                 }
64             }
65         }
66         System.out.println(sum(axis, 0, max));
67     }
68 }