Mdr-C-Tutorial

主题

7. 贪心算法 ​

习题 ​

#30701
⚡3⏳3

电影院在同一个放映厅安排了若干部电影。每部电影用半开区间 [start, end) 表示，实现：

c
#include <stdbool.h>
#include <stddef.h>
#include <stdint.h>

typedef struct {
    int64_t start;
    int64_t end;
} Movie;

bool maximum_movie_count(
    Movie *movies,
    size_t count,
    size_t *out_count
);

要求：

  1. 求一个人从头到尾能够观看的最多电影数量；一部电影结束时可以立即观看此时开始的另一部电影。
  2. 每个区间必须满足 start < end；先检查全部区间，再修改数组。
  3. 可以使用 qsort 原地重排输入数组，并在接口说明中明确这一点。
  4. 比较器不得用两个时间直接相减来决定顺序。
  5. 参数无效时返回 false，并保持输出对象和电影数组不变。
  6. 排序后使用一次线性扫描完成选择，总时间复杂度为 O(nlog⁡n)。
#30702
⚡4⏳3

有若干堆材料，第 i 堆的重量为 weights[i]。每次可以合并两堆材料，代价等于两堆重量之和。实现求合并成一堆所需的最小总代价：

c
#include <stdbool.h>
#include <stddef.h>
#include <stdint.h>

bool minimum_merge_cost(
    const uint64_t *weights,
    size_t count,
    uint64_t *out_cost
);

要求：

  1. count == 0 或 count == 1 时总代价为 0；非空数组指针必须有效。
  2. 不得修改输入数组；任意中间代价或总代价无法用 uint64_t 表示时返回 false，输出对象保持不变。
  3. 每次选择当前最小的两堆合并，并使用优先队列实现 O(nlog⁡n) 时间复杂度。
  4. 说明“先合并最小两项”为什么不会破坏最优性。
#30703
⚡4⏳3

有若干任务，每个任务占用半开时间区间 [start, end)。实现安排这些任务所需的最少资源数量；同一资源上的任务不能重叠：

c
#include <stdbool.h>
#include <stddef.h>
#include <stdint.h>

typedef struct {
    int64_t start;
    int64_t end;
} ResourceTask;

bool minimum_resource_count(
    ResourceTask *tasks,
    size_t count,
    size_t *out_resources
);

要求：

  1. start < end；结束时刻等于下一任务开始时刻时可以复用资源。
  2. 先检查全部区间，再修改任务数组；参数无效时输出对象和任务数组均保持不变。
  3. 以开始时刻排序，并用保存当前最早结束时刻的最小堆计算峰值并发数。
  4. 比较器不得通过两个 int64_t 直接相减决定顺序，时间复杂度为 O(nlog⁡n)。