贪心算法解决活动安排问题：最大化礼堂活动数量

学校礼堂每天都会有许多活动，但有时这些活动的计划时间会发生冲突，需要选择出一些活动进行举办。小刘的工作就是安排学校礼堂的活动，每个时间最多安排一个活动。现在小刘有一些活动计划的时间表，他想尽可能地安排更多的活动，请问他该如何安排？

这个问题可以用贪心算法来解决。贪心算法是一种在每一步选择中都选择当前最优方案，并期望最终得到全局最优解的算法。

算法步骤

排序: 首先，将所有活动按照结束时间进行升序排序。
选择: 从第一个活动开始，选择结束时间最早的活动，并将其加入安排计划。
循环: 遍历剩余活动，选择与当前安排计划中最后一个活动的结束时间不冲突的，且结束时间最早的活动。
重复步骤3: 直到所有活动都被考虑。

Java 代码实现

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

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int M = scanner.nextInt();
        while (M > 0) {
            M--;
            int N = scanner.nextInt();
            ArrayList<Activity> activities = new ArrayList<Activity>();
            for (int i = 0; i < N; i++) {
                int start = scanner.nextInt();
                int end = scanner.nextInt();
                activities.add(new Activity(start, end));
            }
            Collections.sort(activities, new Comparator<Activity>() {
                public int compare(Activity o1, Activity o2) {
                    return o1.end - o2.end;
                }
            });
            int cnt = 0;
            int endtime = -1;
            for (int i = 0; i < activities.size(); i++) {
                if (activities.get(i).start >= endtime) {
                    endtime = activities.get(i).end;
                    cnt++;
                }
            }
            System.out.println(cnt);
        }
    }
}

class Activity {
    int start;
    int end;

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

输入格式

第一行是一个整型数 m (m<100) 表示共有 m 组测试数据。每组测试数据的第一行是一个整数 n (1<n<10000) 表示该测试数据共有 n 个活动。随后的 n 行，每行有两个正整数 Bi, Ei (0<=Bi, Ei<10000), 分别表示第 i 个活动的起始与结束时间（Bi<=Ei)。

输出格式

对于每一组输入，输出最多能够安排的活动数量。每组的输出占一行。

输入样例

输出样例

2
2

总结

贪心算法在活动安排问题中可以有效地选择出最大数量的活动，其时间复杂度为 O(n log n)，其中 n 为活动数量。通过排序和选择活动，算法能够最大化礼堂活动数量，帮助小刘有效地安排学校礼堂的活动计划。