活动安排(贪心)

问题:有n个活动的集合A={1,2,…,n},其中每个活动都要求使用同一资源,如演讲会场等,而在同一时间内只有一个活动能使用这一资源。
求解:安排尽量多项活动在该场地进行,即求A的最大相容子集。

分析:
1.对活动以结束时间增序排序,使剩余可安排时间最大化,以便安排更多的相容活动。
2.遍历排好序的活动,结束时间与下个活动的开始时间进行比较,不相容则继续遍历

package 算法实验;

import java.io.InputStream;
import java.util.*;

/**
 * 测试数据
 11
 1 4
 3 5
 0 6
 5 7
 3 8
 5 9
 6 10
 8 11
 8 12
 12 14
 2 13
 */


class Arr implements Comparable<Arr>{
    public int start;
    public int end;
    /**
     * 按结束时间递增排序
     * @param o
     * @return
     */
    @Override
    public int compareTo(Arr o) {
        // TODO Auto-generated method stub
        if (o.end > this.end) {
            return -1;
        } else if (o.end < this.end) {
            return 1;
        } else {
            return 0;
        }
    }
}

public class Test2 {


    public static void main(String[] args) {

        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        Arr[] arr = new Arr[n];

        for (int i = 0; i < n; i++) {
            arr[i] = new Arr();
            arr[i].start = sc.nextInt();
            arr[i].end = sc.nextInt();
        }
        sc.close();

        Arrays.sort(arr);

        //保存结束时间,与下一个开始时间作比较
        int flag = 0;

        for (int i = 0; i < n; i++) {
            if (flag <= arr[i].start) {
                flag = arr[i].end;
                System.out.println("start:" + arr[i].start + " end:" + arr[i].end);
            }
        }
    }
}
上一篇:解决 groupby 出现错误:TypeError: '<' not supported between instances of 'int' and &


下一篇:python-Dataframe