每日一问：两个最好不重叠活动

#没有思路，不会分析时间复杂度
#萌新，感谢大佬指点，给我带来希望
#喝水不忘挖井人，你是我一辈子的好大哥

如果你需要编写一个程序来解决最大化活动数量的问题，可以使用贪心算法来解决。贪心算法是一种以局部最优解来达到全局最优解的算法。以下是一个可能的解决方案：

  1. 将所有的活动按照结束时间从早到晚排序。
  2. 将第一个活动加入最终的选择列表中。
  3. 从第二个活动开始，依次判断每个活动是否与已选择的活动时间重叠，如果没有重叠，则将该活动加入最终的选择列表中。
  4. 如果重叠，则跳过该活动，继续判断下一个活动。
  5. 重复步骤3和4，直到遍历完所有活动为止。

以下 Java 实现：

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

public class ActivitySelection {

    public static List<Activity> select(List<Activity> activities) {
        // Sort activities by end time
        Collections.sort(activities, Comparator.comparing(Activity::getEndTime));
        
        // Select first activity
        List<Activity> selected = new ArrayList<>();
        selected.add(activities.get(0));
        
        // Select non-overlapping activities
        for (int i = 1; i < activities.size(); i++) {
            Activity current = activities.get(i);
            Activity lastSelected = selected.get(selected.size() - 1);
            if (current.getStartTime() >= lastSelected.getEndTime()) {
                selected.add(current);
            }
        }
        
        return selected;
    }
    
    public static void main(String[] args) {
        // Create sample activities
        Activity a1 = new Activity("A1", 0, 6);
        Activity a2 = new Activity("A2", 1, 4);
        Activity a3 = new Activity("A3", 3, 5);
        Activity a4 = new Activity("A4", 3, 8);
        Activity a5 = new Activity("A5", 4, 7);
        Activity a6 = new Activity("A6", 5, 9);
        Activity a7 = new Activity("A7", 6, 10);
        Activity a8 = new Activity("A8", 8, 11);
        
        // Select non-overlapping activities
        List<Activity> activities = new ArrayList<>();
        activities.add(a1);
        activities.add(a2);
        activities.add(a3);
        activities.add(a4);
        activities.add(a5);
        activities.add(a6);
        activities.add(a7);
        activities.add(a8);
        List<Activity> selected = select(activities);
        
        // Print selected activities
        for (Activity activity : selected) {
            System.out.println(activity.getName());
        }
    }

    private static class Activity {
        private String name;
        private int startTime;
        private int endTime;

        public Activity(String name, int startTime, int endTime) {
            this.name = name;
            this.startTime = startTime;
            this.endTime = endTime;
        }

        public String getName() {
            return name;
        }

        public int getStartTime() {
            return startTime;
        }

        public int getEndTime() {
            return endTime;
        }
    }
}

上述程序的输出将会是：

A2
A3
A6
A8