30701：最多可看电影

题目

从一组电影放映区间中选择数量最多、彼此不重叠的电影。

解析

先按结束时间从早到晚排序；结束时间相同时，再按开始时间排序。线性扫描时，只要当前电影的开始时间不早于上一部已选电影的结束时间，就选择它。

选择最早结束的可行电影，会给后续电影留下不少于其他选择的时间范围。因此每次贪心选择都可以出现在某个最优方案中。比较器使用关系判断，不直接相减，从而避免有符号整数溢出。

解析

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

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

static int compare_movies(
    const void *left_pointer,
    const void *right_pointer
) {
    const Movie *left = left_pointer;
    const Movie *right = right_pointer;

    if (left->end < right->end) {
        return -1;
    }
    if (left->end > right->end) {
        return 1;
    }
    if (left->start < right->start) {
        return -1;
    }
    if (left->start > right->start) {
        return 1;
    }
    return 0;
}

bool maximum_movie_count(
    Movie *movies,
    size_t count,
    size_t *out_count
) {
    if (out_count == NULL ||
        (count > 0 && movies == NULL) ||
        count > SIZE_MAX / sizeof *movies) {
        return false;
    }

    for (size_t i = 0; i < count; ++i) {
        if (movies[i].start >= movies[i].end) {
            return false;
        }
    }

    qsort(
        movies,
        count,
        sizeof *movies,
        compare_movies
    );

    size_t selected = 0;
    int64_t last_end = 0;
    bool have_selection = false;

    for (size_t i = 0; i < count; ++i) {
        if (!have_selection ||
            movies[i].start >= last_end) {
            ++selected;
            last_end = movies[i].end;
            have_selection = true;
        }
    }

    *out_count = selected;
    return true;
}

来源与改编

题型改编自 CSES Problem Set 的 Movie Festival，采用 CC BY-NC-SA 4.0；本题改为原地排序的 C 接口，并补充区间校验与比较器约束。