P2506. 模拟消息队列

解题思路

题目概述

本题为纯模拟题，题目数据量不大，n * m 的最大值为 100 * 10 = 10^3，可以考虑直接暴力模拟的方式来完成。

题意理解

题目描述比较长，需要对题意进行细致的理解。

消息数据的处理

第一行输入的 2N 个数字表示的是 N 个消息的推送时间和内容。如示例一中的：

表示一共有 5 个消息。如果把消息的推送时间和内容储存在 msg_lst 中，存在：

为了方便按照时间先后顺序对消息进行处理，我们可以对 msg_lst 根据二元组的第一个元素即时间进行升序排序：

可以得到结果：

人员数据的处理

第二行输入的 2M 个数字表示的是 M 个人开始订阅和取消订阅的时刻。如示例一中的：

表示一共有 2 个人。如果把这些人开始订阅和取消订阅的时刻储存在 person_lst 中，存在：

另外，题目中包含这样一句话：

> 输入中消费者按优先级升序排列

表示在 person_lst 中，位置越靠后的人优先级越高。

模拟推送过程

剩下的工作就非常简单了，对于排序后的消息列表 msg_lst，我们遍历每一个消息。

对于每一个消息，我们再逆序遍历 person_lst，按照优先级从大到小考虑每一个人的开始和取消订阅时间 start 和 end。

若消息的推送时间 msg_time 恰好位于这个人开始和取消订阅的时间之间，那么该消息推送给这个人。

整理为代码即：

复杂度分析 设消息条数为 n，订阅者人数为 m（题解开头提到本题数据量级约为 n ≤ 100、m ≤ 10）。

• 时间复杂度：O(n log n + n × m)。先对 msg_lst 按发送时间排序，代价 O(n log n)；随后对每条消息逆序扫描一遍订阅者列表，寻找优先级最高且订阅区间 [start, end) 覆盖该发送时刻的人，找到即 break，单条消息最坏要检查 m 个人，这一段共 O(n × m)。最后逐个订阅者输出收到的消息，总条数不超过 n。按题目给的数据量，总计算量在 10³ 量级，非常宽裕。
• 空间复杂度：O(n + m)。msg_lst 与 person_lst 分别存放 n 条消息和 m 个订阅区间，答案数组 ans 中所有推送记录合计不超过 n 条。