贪心算法之活动选择

问题： 有n个需要在同一天使用同一个教室的活动a1, a2, …, an，教室同一时刻只能由一个活动使用。每个活动a[i]都有一个 开始时间s[i]和结束时间f[i]。一旦被选择后，活动a[i]就占据半开时间区间[s[i],f[i])。如果[s[i],f[i])和[s[j],f[j])互不重叠，a[i]和a[j]两个活动就可以被安排在这一天。求使得尽量多的活动能不冲突的举行的最大数量。

贪心策略 ：
1.每次都选择开始时间最早的活动，不能得到最优解。
2. 每次都选择持续时间最短的活动，不能得到最优解。
3.每次选取结束时间最早的活动，可以得到最优解。按这种方法选择，可以为未安排活动留下尽可能多的时间。如下图所示的 活动集合S，其中各项活动按照结束时间单调递增排序。

代码：

import java.util.Arrays;
import java.util.Comparator;
import java.util.Scanner;

public class test{
    static class myComparator implements Comparator {
        //按起点递增排序
        public int compare(int[] a,int[] b){
            return a[1]-b[1];
        }
    }
    public static int greedyActivitySelector(int[][] act){
        //每次选择最早结束的活动
        int num=1;
        int i=0;
        for (int j = 1; j =  act[i][1]){
                i=j;
                num++;
            }
        }
        return num;
    }

    public static void main(String[] args) {
        Scanner scanner=new Scanner(System.in);
        int number=scanner.nextInt();
        int[][] act=new int[number][2];
        int idx=0;
        for (int i = 0; i  
运行结果：