P9330 [JOISC 2023 Day1] Festivals in JOI Kingdom 2 题解

· · 题解

传送门

这是一道贪心算法的问题。

首先将所有的节日按照结束时间从小到大进行排序。对于每个节日，我们可以将其安排在结束时间最早的且未被安排过的一天，如果有多个选择，我们选择结束时间最早的一天。

为了实现这个贪心策略，可以使用一个数组记录每个日期是否被使用，从日期最小的开始遍历，找到第一个未被使用的日期即可。如果当前的日期已被使用，则继续向下一个日期遍历。

具体实现时，我们可以首先将所有节日按结束时间排序，然后定义一个数组 user，初始化为 false。接着依次遍历每个节日，对于每个节日，从结束时间往前逆推找到第一个未被使用的日期，将其标记为使用，并在 ans 中加入这个日期。

最后输出 ans 的长度即可。

时间复杂度为 O(n^2)，但由于数据范围较小，可以通过本题。