固定最早开始任务为首项的贪心活动选择Java实现问题

你的代码存在两个核心逻辑错误，导致输出不符合要求：

• 初始活动选择逻辑和需求不符：需求要求必须选择开始时间最早的活动作为首个选中项，但当前代码的优先队列按活动结束时间升序排序，第一次取出的是全局结束最早的活动（开始时间1、结束时间2），直接跳过了开始时间最早的目标活动（开始时间0、结束时间6），初始选择错误后续结果必然不对。
• 数据字段语义混乱：存储活动时你将结束时间存在Pair的first字段、开始时间存在second字段，后续排序、取值时没有做对应语义对齐，进一步放大了逻辑错误。

按照你的定制规则，要得到最多数量的非重叠活动集合，执行流程固定为：

• 第一步遍历全量活动，筛选出开始时间最早的活动作为第一个选中项，记录该活动的结束时间作为后续重叠判断的基准值。
• 把剩余所有活动按结束时间升序排列，这是贪心求最多非重叠活动的核心规则：每次选和上一个已选活动不重叠、结束时间最早的活动，能给后续活动留出最多的可用时间，保证最终选中的活动总数最大。
• 依次遍历排序后的剩余活动，只要当前活动的开始时间大于等于上一个选中活动的结束时间，就选中该活动，同时更新时间基准为当前活动的结束时间，直到遍历完所有活动。

import java.io.*;
import java.lang.*;
import java.util.*;
 
class GFG {
  // 活动实体类，统一字段语义：start存活动开始时间，end存活动结束时间
  static class Activity {
    int start;
    int end;
 
    Activity(int start, int end) {
      this.start = start;
      this.end = end;
    }
  }
 
  static void SelectActivities(int s[], int f[]) {
    ArrayList<Activity> selected = new ArrayList<>();
    // 查找开始时间最早的活动作为首个选中项
    int earliestStartIndex = 0;
    for (int i = 1; i < s.length; i++) {
      if (s[i] < s[earliestStartIndex]) {
        earliestStartIndex = i;
      }
    }
    Activity first = new Activity(s[earliestStartIndex], f[earliestStartIndex]);
    selected.add(first);
    int lastEndTime = first.end;

    // 剩余活动按结束时间升序存入优先队列
    PriorityQueue<Activity> activityQueue = new PriorityQueue<>(Comparator.comparingInt(act -> act.end));
    for (int i = 0; i < s.length; i++) {
      if (i == earliestStartIndex) continue; // 跳过已经选中的首个活动
      activityQueue.add(new Activity(s[i], f[i]));
    }

    // 贪心筛选后续不重叠活动
    while (!activityQueue.isEmpty()) {
      Activity current = activityQueue.poll();
      if (current.start >= lastEndTime) {
        selected.add(current);
        lastEndTime = current.end;
      }
    }

    // 打印结果
    System.out.println("Following Activities should be selected. \n");
    for (Activity act : selected) {
      System.out.println("Activity started at: " + act.start + " and ends at  " + act.end);
    }
  }
 
  public static void main(String[] args) {
    int s[] = { 1, 3, 0, 5, 8, 5 };
    int f[] = { 2, 4, 6, 7, 9, 9 };
    SelectActivities(s, f);
  }
}

运行上述代码，输出和期望完全一致：

Following Activities should be selected. 

Activity started at: 0 and ends at  6
Activity started at: 8 and ends at  9

内容的提问来源于stack exchange，提问作者Programmer