运用贪心算法求解活动安排问题java

活动安排问题是一个经典的贪心算法问题。假设有n个活动，每个活动都有一个开始时间和结束时间，现在要在这些活动中选出尽可能多的活动，使得它们不冲突（即它们的时间段没有重叠）。我们可以用贪心算法求解这个问题，具体步骤如下：

1. 将所有活动按照结束时间从小到大排序。
2. 选择第一个活动，并将其加入解集合中。
3. 依次考虑剩余的活动，如果当前活动的开始时间晚于等于解集合中最后一个活动的结束时间，则将该活动加入解集合中。
4. 重复步骤3，直到所有活动都被考虑完毕。

下面是Java代码实现：

import java.util.*;

class Activity implements Comparable<Activity> {
    int start;
    int end;

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

    @Override
    public int compareTo(Activity other) {
        return this.end - other.end;
    }
}

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

        Collections.sort(activities);
        result.add(activities.get(0));

        for (int i = 1; i < activities.size(); i++) {
            if (activities.get(i).start >= result.get(result.size() - 1).end) {
                result.add(activities.get(i));
            }
        }

        return result;
    }

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

        List<Activity> selected = select(activities);
        System.out.println("Selected activities:");
        for (Activity activity : selected) {
            System.out.println(activity.start + " " + activity.end);
        }
    }
}

输出结果为：

Selected activities:
1 4
5 7
8 11
12 14