Pascal 实现电视节目最多观看数——经典贪心算法落地详解

这是一个经典的 **区间调度（Activity Selection）问题**，目标是： ✅ 在互不重叠（允许端点相接，如 `[1,3]` 和 `[3,4]` ✅ 允许）的前提下，**选择最多数量的节目**。 👉 **贪心策略最优解：按结束时间升序排序，每次选当前最早结束且与上一个不冲突的节目。** --- ### ✅ Pascal 解法（标准、简洁、AC-ready） > ⚠️ 注意：Pascal 中数组下标从 `1` 开始更安全；使用 `qsort` 需自定义比较函数（Free Pascal 支持 `system` 单元的 `qsort` 或手动快排）；但为清晰 & 兼容性，我们用 **简单选择排序 + 手动模拟贪心**（n ≤ 100，完全足够）。 ```pascal program TVSchedule; type Program = record s, e: longint; end; var n, i, j, count, last_end: longint; a: array[1..100] of Program; tmp: Program; begin while true do begin readln(n); if n = 0 then break; // 读入 n 个节目 for i := 1 to n do readln(a[i].s, a[i].e); // ✅ 关键：按结束时间 e 升序排序（冒泡/选择均可，n≤100） for i := 1 to n - 1 do for j := i + 1 to n do if a[j].e < a[i].e then begin tmp := a[i]; a[i] := a[j]; a[j] := tmp; end; // ✅ 贪心选择：取第一个（最早结束），然后每次找 s >= 上一个 e 的最早结束者 count := 0; last_end := -1; // 初始无节目，设 last_end = -1（所有 s ≥ 0，所以第一个必可选） for i := 1 to n do if a[i].s >= last_end then begin count := count + 1; last_end := a[i].e; end; writeln(count); end; end. ``` --- ### ✅ 为什么这个贪心正确？（一句话证明） > **“选择当前最早结束的节目，不会比任何最优解差”** —— 因为它给后续留出最多时间空间，数学归纳可证全局最优。 --- ### ✅ 输入输出验证（样例） 输入： ``` 12 1 3 3 4 0 7 3 8 15 19 15 20 10 15 8 18 6 12 5 10 4 14 2 9 0 ``` 排序后（按 `e` 升序）前几项： ``` (1,3) e=3 (3,4) e=4 (0,7) e=7 (5,10) e=10 (10,15) e=15 (15,19) e=19 ... ``` 贪心选： - `(1,3)` → count=1, last_end=3 - `(3,4)` → 3≥3 ✅ → count=2, last_end=4 - `(0,7)` → 0<4 ❌ skip - `(5,10)` → 5≥4 ✅ → count=3, last_end=10 - `(10,15)` → 10≥10 ✅ → count=4, last_end=15 - `(15,19)` → 15≥15 ✅ → count=5 ✅ 输出 `5` —— 完全匹配样例！ --- ### 💡 Pascal 使用提示 | 事项 | 说明 | |------|------| | 📦 编译器推荐 | [Free Pascal Compiler (fpc)](https://www.freepascal.org/)，支持 `writeln`, `readln`, `longint`（32位，足够 `n≤100`, 时间≤10⁹） | | ⏱️ 时间复杂度 | $ O(n^2) $ 排序 + $ O(n) $ 贪心 = 总 $ O(n^2) $，n≤100 → 最多 10⁴ 次操作，飞快 | | 🧩 可选升级 | 若想用快排，可调用 `system.qsort`（需 `{$mode objfpc}`）或写递归快排，但非必须 | --- 需要我为你提供： - ✅ **C++ / Python / Java 对应版本（含详细注释）** - ✅ **该题的动态规划解法（对比贪心，理解为何 DP 不必要）** - ✅ **画图演示贪心选择过程（区间覆盖示意图）** - ✅ **生成 Pascal 测试数据脚本（.inp/.out 自动对拍）** 欢迎随时说 👇 祝你 Pascal 编译一次过，AC 一发入魂！📺✨ ######[AI写代码神器 | 1212点数解答 | 2026-03-18 17:59:37]