活动安排问题贪心算法java实现

活动安排问题是一道经典的贪心算法问题，它的目标是从一组活动中选择出最多的相互兼容的活动。以下是活动安排问题的具体描述：

有n个活动要占用同一块资源（如一个房间），每个活动ai有一个开始时间si和结束时间fi（si<fi），只有在时间区间[si,fi)内才能进行这个活动。若区间[si,fi]与区间[sj,fj]不相交，则称活动ai与aj是相互兼容的。你的目标是选出尽量多的相互兼容的活动。

下面是该问题的贪心算法实现过程（假设所有活动按照结束时间从小到大排序）：

1. 选取结束时间最早的活动；
2. 从剩余的活动中选取与已选中的最后一个活动相兼容且结束时间最早的活动；
3. 重复步骤2，直到没有剩余的活动。

以下是Java代码实现：

import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;
import java.util.List;

public class ActivitySelection {
    public static List<Activity> activitySelection(List<Activity> activities) {
        List<Activity> selectedActivities = new ArrayList<>();
        if (activities.isEmpty()) {
            return selectedActivities;
        }

        // 将所有活动按照结束时间从小到大排序
        Collections.sort(activities, new Comparator<Activity>() {
            @Override
            public int compare(Activity o1, Activity o2) {
                return o1.getEnd() - o2.getEnd();
            }
        });

        // 选取第一个结束时间最早的活动
        selectedActivities.add(activities.get(0));
        int lastSelectedEnd = activities.get(0).getEnd();

        // 从剩余的活动中选取与已选中的最后一个活动相兼容且结束时间最早的活动
        for (int i = 1; i < activities.size(); i++) {
            Activity activity = activities.get(i);
            if (activity.getStart() >= lastSelectedEnd) {
                selectedActivities.add(activity);
                lastSelectedEnd = activity.getEnd();
            }
        }

        return selectedActivities;
    }

    public static void main(String[] args) {
        List<Activity> activities = new ArrayList<>();
        activities.add(new Activity(1, 4));
        activities.add(new Activity(3, 5));
        activities.add(new Activity(0, 6));
        activities.add(new Activity(5, 7));
        activities.add(new Activity(3, 8));
        activities.add(new Activity(5, 9));
        activities.add(new Activity(6, 10));
        activities.add(new Activity(8, 11));
        activities.add(new Activity(8, 12));
        activities.add(new Activity(2, 13));
        activities.add(new Activity(12, 14));

        List<Activity> selectedActivities = activitySelection(activities);

        System.out.println("选中的活动：");
        for (Activity activity : selectedActivities) {
            System.out.println(activity);
        }
    }
}

class Activity {
    private int start;
    private int end;

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

    public int getStart() {
        return start;
    }

    public int getEnd() {
        return end;
    }

    @Override
    public String toString() {
        return "[" + start + ", " + end + "]";
    }
}