活动选择(java)

解题思路:

（内容由ai生成）

定义活动类 (Activity):

这个类有三个属性：id（活动的标识符）、start（活动的开始时间）和finish（活动的结束时间）。

类实现了Comparable<Activity>接口，以便能够根据活动的结束时间对活动列表进行排序。

主类 (活动安排):

在main方法中，首先初始化一个计数器count为1，因为即使我们不检查第一个活动，它也会被选中（由于按结束时间排序，第一个活动总是可选的）。

使用Scanner从用户那里读取活动数量n，然后对于每个活动，读取其开始和结束时间，并将其添加到activity列表中。

使用Collections.sort(activity)对活动列表进行排序。由于Activity类实现了Comparable接口，并根据结束时间进行了比较，因此这会按结束时间的升序对活动进行排序。

初始化fin为第一个活动的结束时间。这个变量将用于跟踪最后一个被选择活动的结束时间。

遍历排序后的活动列表。对于每个活动，检查其开始时间是否大于或等于fin（即它是否与最后一个被选择的活动重叠）。如果是这样，则选择该活动（通过增加计数器并更新fin为该活动的结束时间）。

最后，打印出被选择的活动数量。

这种方法的关键在于按结束时间对活动进行排序，并始终选择下一个不与已选择活动重叠的活动。这样可以确保所选活动的数量是最大的。注意，这种贪心算法在这里是有效的，因为它利用了这样一个事实：由于活动是按结束时间排序的，所以总是选择下一个可行的活动（即开始时间晚于或等于当前fin的活动）会导致最优解。

注意事项:

参考代码:

import java.util.ArrayList;
import java.util.Collection;
import java.util.Collections;
import java.util.Scanner;

class Activity implements Comparable<Activity> {
    int id;
    int start;
    int finish;

    public Activity(int id, int start, int finish) {
        this.id = id;
        this.start = start;
        this.finish = finish;
    }

    @Override
    public int compareTo(Activity other) {
        return Integer.compare(this.finish, other.finish);
    }
}
public class Main {
    public static void main(String[] args) {
        int count = 1;
        Scanner sc = new Scanner(System.in);
        ArrayList<Activity> activity = new ArrayList<>();
        int n = sc.nextInt();
        for (int i = 0; i < n; i++) {
            int s = sc.nextInt();
            int e = sc.nextInt();
            activity.add(new Activity(i+1,s,e));
        }
        Collections.sort(activity);
        int fin = activity.get(0).finish;
        for (int i = 1; i < activity.size(); i++) {
            if(activity.get(i).start >= fin){
                fin = activity.get(i).finish;
                count++;
            }
        }
        System.out.println(count);
    }
}