每日算法 — 使用java实现活动选择：贪心策略与区间调度最优解

活动选择问题是贪心算法的经典入门案例。假设你有一系列需要使用同一间会议室的活动，每个活动有开始时间和结束时间，如何安排才能在不冲突的前提下参加最多的活动？本文用Java实现贪心解法，深入剖析”最早结束优先”策略的最优性证明，并扩展至多会议室调度问题。

一、问题描述

给定n个活动的集合，每个活动i都有一个开始时间s[i]和结束时间f[i]。这些活动都需要使用同一资源（如同一间会议室），且同一时间只能有一个活动使用该资源。如果两个活动的时间区间不重叠，则称它们是兼容的。目标是找出一个最大兼容活动子集。

示例数据

直观上看，选择最早结束的活动（A，结束于4），就能为后续活动留下更多时间，接下来在4之后最早结束的是D（结束于7），然后是G（结束于10），最后是K（结束于14）。因此最优解为 {A, D, G, K}，共4个活动。

二、贪心策略：最早结束优先

活动选择问题的贪心策略非常简单：每次都选择结束时间最早且与已选活动兼容的活动。

为什么这个策略是最优的？

设贪心算法第一个选择的是活动1（全局最早结束的活动）。假设存在一个最优解S，S中的第一个活动是活动k。

• 如果k = 1，则贪心选择恰好与最优解的第一步一致。
• 如果k ≠ 1，由于活动1的结束时间 ≤ 活动k的结束时间，用活动1替换活动k后，得到的新集合S'仍然是一组兼容活动，且活动数量不变。因此S'也是最优解。

这说明贪心选择性质成立：存在一个最优解包含了贪心选择的第一个活动。将问题规约为子问题（在第一个活动结束之后开始的所有活动）后递归求解即可。

三、基础实现：单次资源调度

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

/**
 * 活动选择问题 - 贪心算法实现
 * 目标：在单一资源约束下，选出最多数量的互不冲突活动
 */
public class ActivitySelection {

    /**
     * 活动类，封装活动的名称、开始时间和结束时间
     */
    static class Activity {
        String name;    // 活动名称
        int start;      // 开始时间
        int finish;     // 结束时间

        Activity(String name, int start, int finish) {
            this.name = name;
            this.start = start;
            this.finish = finish;
        }

        @Override
        public String toString() {
            return String.format("%s[%d, %d]", name, start, finish);
        }
    }

    /**
     * 贪心算法求解活动选择问题
     * 核心思想：按结束时间升序排序，每次选择最早结束且兼容的活动
     *
     * @param activities 活动数组
     * @return 最大兼容活动子集
     */
    public static List<Activity> selectActivities(Activity[] activities) {
        // 防御性拷贝，避免修改原始数组
        Activity[] sorted = activities.clone();

        // 按结束时间升序排序，这是贪心策略的核心前提
        Arrays.sort(sorted, Comparator.comparingInt(a -> a.finish));

        List<Activity> result = new ArrayList<>();
        if (sorted.length == 0) {
            return result;
        }

        // 贪心选择：第一个活动一定是结束时间最早的
        Activity lastSelected = sorted[0];
        result.add(lastSelected);

        // 遍历剩余活动，选择开始时间不小于上一个选中活动结束时间的活动
        for (int i = 1; i < sorted.length; i++) {
            // 兼容条件：当前活动的开始时间 >= 上一个选中活动的结束时间
            if (sorted[i].start >= lastSelected.finish) {
                result.add(sorted[i]);
                lastSelected = sorted[i]; // 更新最后选中的活动
            }
        }

        return result;
    }

    /**
     * 主程序：演示活动选择算法的完整流程
     */
    public static void main(String[] args) {
        Activity[] activities = {
            new Activity("A", 1, 4),
            new Activity("B", 3, 5),
            new Activity("C", 0, 6),
            new Activity("D", 5, 7),
            new Activity("E", 3, 8),
            new Activity("F", 5, 9),
            new Activity("G", 6, 10),
            new Activity("H", 8, 11),
            new Activity("I", 8, 12),
            new Activity("J", 2, 13),
            new Activity("K", 12, 14)
        };

        System.out.println("=== 活动选择问题演示 ===\n");
        System.out.println("原始活动列表（按输入顺序）：");
        for (Activity a : activities) {
            System.out.println("  " + a);
        }

        List<Activity> selected = selectActivities(activities);

        System.out.println("\n贪心策略：按结束时间排序后依次选择最早结束且兼容的活动");
        System.out.println("选中的活动序列：");
        for (Activity a : selected) {
            System.out.println("  " + a);
        }
        System.out.println("\n最多可安排 " + selected.size() + " 个活动");
    }
}

四、扩展实现：会议室安排问题

如果问”至少需要多少间会议室才能安排所有活动”，这是一个经典的区间划分问题。该问题可用贪心+优先队列解决：按开始时间排序，维护每间会议室的最后占用时间，如果某活动可以放入已有会议室（开始时间 ≥ 某会议室最后结束时间），则复用；否则新开一间会议室。

import java.util.Arrays;
import java.util.Comparator;
import java.util.PriorityQueue;

/**
 * 会议室安排问题 - 最少会议室数量
 * 变体：所有活动都必须举行，求最少需要多少间会议室
 */
public class MeetingRooms {

    static class Meeting {
        int start;
        int end;

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

    /**
     * 计算最少需要的会议室数量
     * 算法：按开始时间排序，用小根堆维护各会议室的结束时间
     *
     * @param meetings 会议数组
     * @return 最少会议室数量
     */
    public static int minMeetingRooms(Meeting[] meetings) {
        if (meetings == null || meetings.length == 0) {
            return 0;
        }

        // 按开始时间升序排序
        Arrays.sort(meetings, Comparator.comparingInt(m -> m.start));

        // 小根堆：存储每个会议室的结束时间
        PriorityQueue<Integer> endTimes = new PriorityQueue<>();

        for (Meeting m : meetings) {
            // 如果最早释放的会议室在当前会议开始前已结束，复用它
            if (!endTimes.isEmpty() && endTimes.peek() <= m.start) {
                endTimes.poll(); // 移除旧结束时间
            }
            // 分配会议室（新的或复用的），记录当前会议的结束时间
            endTimes.offer(m.end);
        }

        // 堆的大小即为最少会议室数量
        return endTimes.size();
    }

    public static void main(String[] args) {
        Meeting[] meetings = {
            new Meeting(0, 30),
            new Meeting(5, 10),
            new Meeting(15, 20)
        };

        System.out.println("=== 会议室安排问题 ===");
        System.out.println("给定会议时间区间，计算最少需要的会议室数量");
        for (Meeting m : meetings) {
            System.out.printf("  会议 [%d, %d]%n", m.start, m.end);
        }
        System.out.println("\n最少需要会议室: " + minMeetingRooms(meetings) + " 间");
        // 解释：[0,30]占用一间，[5,10]冲突需第二间，[15,20]可在[5,10]结束后复用第二间
    }
}

五、带权活动选择：动态规划对比

如果每个活动都有一个权重（如收益），目标是使选中活动的总权重最大，则贪心策略不再适用。此时需要使用动态规划。将活动按结束时间排序后，设dp[i]表示考虑前i个活动时的最大权重，状态转移方程为：

dp[i] = max(dp[i-1], weight[i] + dp[p(i)])

其中p(i)是活动i之前最后一个与其兼容的活动下标。

/**
 * 带权活动选择 - 动态规划解法
 * 当每个活动有不同收益时，贪心失效，需用DP
 */
public class WeightedActivitySelection {

    static class Activity {
        int start, finish, weight;
        Activity(int s, int f, int w) {
            this.start = s;
            this.finish = f;
            this.weight = w;
        }
    }

    /**
     * 二分查找：找到最后一个结束时间 <= 当前活动开始时间的活动
     */
    private static int binarySearch(Activity[] acts, int endTime) {
        int lo = 0, hi = acts.length - 1, res = -1;
        while (lo <= hi) {
            int mid = (lo + hi) >>> 1;
            if (acts[mid].finish <= endTime) {
                res = mid;
                lo = mid + 1;
            } else {
                hi = mid - 1;
            }
        }
        return res;
    }

    public static int maxWeight(Activity[] activities) {
        java.util.Arrays.sort(activities, java.util.Comparator.comparingInt(a -> a.finish));

        int n = activities.length;
        // dp[i] 表示考虑前i个活动（0~i-1）的最大权重
        int[] dp = new int[n + 1];

        for (int i = 1; i <= n; i++) {
            Activity curr = activities[i - 1];
            // 找到与当前活动兼容的最后一个活动
            int compatibleIndex = binarySearch(activities, curr.start);
            int includeWeight = curr.weight + (compatibleIndex >= 0 ? dp[compatibleIndex + 1] : 0);
            int excludeWeight = dp[i - 1];
            dp[i] = Math.max(includeWeight, excludeWeight);
        }

        return dp[n];
    }

    public static void main(String[] args) {
        Activity[] acts = {
            new Activity(1, 3, 5),
            new Activity(2, 5, 6),
            new Activity(4, 6, 5),
            new Activity(6, 7, 4),
            new Activity(5, 8, 11),
            new Activity(7, 9, 2)
        };
        System.out.println("带权活动选择最大收益: " + maxWeight(acts));
        // 最优解为选择 [1,3]=5 + [4,6]=5 + [6,7]=4 = 14，或 [2,5]=6 + [6,7]=4 = 10
        // 实际是 [1,3]=5 + [4,6]=5 + [6,7]=4 = 14
    }
}

六、复杂度分析

贪心算法之所以高效，是因为排序后只需一次线性扫描即可得到最优解。相比之下，动态规划虽然能解决更一般的带权问题，但时间和空间开销都更大。

七、应用场景

• 课程表排课：在有限的教室和时间段内安排最多的课程
• 广播频段分配：为广播电台分配互不干扰的频段
• 任务调度：单线程CPU上调度执行时间互不重叠的最大任务数
• 资源预订：酒店房间、会议室、体育场馆等有限资源的预订管理
• 广播节目编排：在固定时段内编排最多的节目内容

八、总结

活动选择问题是理解贪心算法的绝佳切入点：

1. 贪心选择性质保证了局部最优（最早结束）能导向全局最优
2. 最优子结构保证了解决子问题后合并即可得到原问题最优解
3. 贪心算法的时间复杂度主要取决于排序，即 O(n log n)
4. 当问题加入权重维度后，贪心策略失效，需要转向动态规划

掌握活动选择问题，不仅能应对各类算法面试，更能在实际工程中的调度、排期等场景快速建模求解。从单一资源调度到多资源分配，从等权到带权，活动选择问题的各个变体覆盖了贪心与DP两大核心范式，值得深入理解。