一、真题

题目描述：

让我们来模拟一个消息队列的运作，有一个发布者和若干消费者，发布者会在给定的时刻向消息队列发送消息。若此时消息队列有消费者订阅，这个消息会被发送到订阅的消费者中优先级最高（输入中消费者按优先级升序排列）的一个。

若此时没有订阅的消费者，该消息被消息队列丢弃。消费者则会在给定的时刻订阅消息队列或取消订阅。当消息发送和订阅发生在同一时刻时，先处理订阅操作，即同一时刻订阅的消费者成为消息发送的候选者。当消息发送和取消订阅发生在同一时刻时，先处理取消订阅操作，即消息不会被发送到同一时刻取消订阅的消费者。

输入描述

输入为两行

第一行为 2N 个正整数，代表发布者发送的 N 个消息的时刻和内容（为方便解析，消息内容也用正整数表示）。第一个数字是第一条消息的发送时刻，第二个数字是第一条消息的内容，以此类推。用例保证发送时刻不会重复，但注意消息并没有按照发送时刻排列。

第二行为 2M 个正整数，代表 M 个消费者订阅和取消订阅的时刻。第一个数字是第一个消费者订阅的时刻，第二个数字是第一个消费者取消订阅的时刻，以此类推。用例保证每个消费者的取消订阅时刻大于订阅时刻，消费者按优先级升序排列。

两行的数字都由空格分隔。N 不超过 100，M 不超过 10，每行的长度不超过 1000 字符。

输出描述

输出为 M 行，依次为 M 个消费者收到的消息内容，消息内容按接收到的顺序排列，且由空格分隔。若某个消费者没有收到任何消息，则对应的行输出 -1。

示例 1：

输入

2 22 1 11 4 44 5 55 3 33

输出

11 33 44 55
22

说明

消息11在1时刻到达，此时只有第一个消费者订阅，消息发送给它，
消息22在2时刻到达，此时两人消费者都订阅了，消息发送给优先级最高的第二个消费者：
消息33在时刻3到达，此时只有第一个消费者订阅，消息发送给它；
余下的消息按规则也是发送给第一个消费者。

示例2：

输入

5 64 11 64 9 97
9 11 4 9

输出

97
64

说明

消息64在5时刻到达，此时只有第二个消费者订阅，消息发送给它
消息97在9时刻到达，此时只有第一消费者订阅（因为第二个消费者刚好在9时刻取消订阅），消息发送给它。11时刻也到达了一个内容为64的消息，不过因为没有消费者订阅，消息被丢弃。

二、核心解题思路：事件驱动模拟💡

这道题的本质是离散事件模拟（Discrete Event Simulation）。我们需要将所有操作（发消息、订阅、取消）统一看作“事件”，并按时间轴推进。

步骤 1：定义事件类型与优先级

为了正确处理同一时刻的逻辑，我们将所有操作转化为事件，并定义排序规则：

• 事件类型：
  • CANCEL_SUB (取消订阅)
  • ADD_SUB (新增订阅)
  • SEND_MSG (发送消息)
• 同一时刻的处理优先级（排序关键字）：
  1. 时间 (time)：升序。
  2. 事件类型 (type)：
     • CANCEL_SUB (优先级最高，最先执行)
     • ADD_SUB (次之)
     • SEND_MSG (最后执行)
  • 注：对于同类型的多个事件（如两个消费者同时取消），顺序通常不影响结果，但为了稳定，可按消费者ID排序。

步骤 2：构建事件列表

1. 解析消息：将输入的 N 条消息转换为 N 个 SEND_MSG 事件。注意：输入未排序，必须记录原始顺序或直接存入列表后统一排序。
2. 解析消费者：将 M 个消费者的订阅/取消动作转换为 2M 个事件：
   • ADD_SUB (时间=订阅时刻, 消费者ID= i )
   • CANCEL_SUB (时间=取消时刻, 消费者ID= i )
3. 统一排序：将所有事件放入一个大列表，按照上述规则排序。

步骤 3：模拟执行

1. 初始化一个集合/数组 activeSubscribers 记录当前已订阅的消费者ID。
2. 初始化 MM 个列表 receivedMessages[i] 记录每个消费者收到的消息。
3. 遍历排序后的事件列表：
   • 若是 CANCEL_SUB：从 activeSubscribers 移除该消费者。
   • 若是 ADD_SUB：将该消费者加入 activeSubscribers。
   • 若是 SEND_MSG：
     • 检查 activeSubscribers 是否为空。
     • 若不为空，找出其中ID最大的消费者（因为输入是按优先级升序，ID越大优先级越高）。
     • 将消息内容添加到该消费者的 receivedMessages 列表中。

步骤 4：输出结果

• 遍历 MM 个消费者，若 receivedMessages 为空，输出 -1。
• 否则，按接收顺序输出消息内容，空格分隔。

---

三、Java 语言实现

import java.util.*;
import java.io.*;

public class Main {

    // 事件类型常量
    static final int TYPE_CANCEL = 0; // 优先级最高，最先执行
    static final int TYPE_SUBSCRIBE = 1;
    static final int TYPE_SEND = 2;   // 优先级最低，最后执行

    static class Event implements Comparable<Event> {
        int time;
        int type;
        int consumerId; // 仅订阅/取消事件有效
        int messageContent; // 仅发送事件有效

        public Event(int time, int type, int consumerId, int messageContent) {
            this.time = time;
            this.type = type;
            this.consumerId = consumerId;
            this.messageContent = messageContent;
        }

        @Override
        public int compareTo(Event o) {
            // 1. 时间升序
            if (this.time != o.time) {
                return Integer.compare(this.time, o.time);
            }
            // 2. 类型优先级：CANCEL(0) < SUBSCRIBE(1) < SEND(2)
            // 数值越小越靠前，符合题目要求的执行顺序
            if (this.type != o.type) {
                return Integer.compare(this.type, o.type);
            }
            // 3. 同类型事件，按消费者ID排序（可选，保证稳定性）
            return Integer.compare(this.consumerId, o.consumerId);
        }
    }

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        
        // 读取第一行：消息
        if (!scanner.hasNextLine()) return;
        String line1 = scanner.nextLine();
        String[] msgParts = line1.trim().split("\\s+");
        
        // 读取第二行：消费者
        if (!scanner.hasNextLine()) return;
        String line2 = scanner.nextLine();
        String[] subParts = line2.trim().split("\\s+");

        List<Event> events = new ArrayList<>();

        // 解析消息事件 (每2个数字一组：时刻，内容)
        for (int i = 0; i < msgParts.length; i += 2) {
            int time = Integer.parseInt(msgParts[i]);
            int content = Integer.parseInt(msgParts[i+1]);
            events.add(new Event(time, TYPE_SEND, -1, content));
        }

        // 解析消费者事件 (每2个数字一组：订阅时刻，取消时刻)
        // 消费者ID从0开始，对应优先级升序（ID越大优先级越高）
        int m = subParts.length / 2;
        for (int i = 0; i < m; i++) {
            int subTime = Integer.parseInt(subParts[2*i]);
            int cancelTime = Integer.parseInt(subParts[2*i+1]);
            
            // 订阅事件
            events.add(new Event(subTime, TYPE_SUBSCRIBE, i, 0));
            // 取消事件
            events.add(new Event(cancelTime, TYPE_CANCEL, i, 0));
        }

        // 核心：事件排序
        Collections.sort(events);

        // 模拟过程
        Set<Integer> activeSubscribers = new HashSet<>();
        List<List<Integer>> receivedMessages = new ArrayList<>();
        for (int i = 0; i < m; i++) {
            receivedMessages.add(new ArrayList<>());
        }

        for (Event e : events) {
            if (e.type == TYPE_CANCEL) {
                activeSubscribers.remove(e.consumerId);
            } else if (e.type == TYPE_SUBSCRIBE) {
                activeSubscribers.add(e.consumerId);
            } else if (e.type == TYPE_SEND) {
                if (!activeSubscribers.isEmpty()) {
                    // 找优先级最高的消费者 -> ID最大的那个
                    int bestConsumer = -1;
                    for (int id : activeSubscribers) {
                        if (id > bestConsumer) {
                            bestConsumer = id;
                        }
                    }
                    receivedMessages.get(bestConsumer).add(e.messageContent);
                }
                // 若为空，消息丢弃，不做操作
            }
        }

        // 输出结果
        for (int i = 0; i < m; i++) {
            List<Integer> msgs = receivedMessages.get(i);
            if (msgs.isEmpty()) {
                System.out.println("-1");
            } else {
                StringBuilder sb = new StringBuilder();
                for (int k = 0; k < msgs.size(); k++) {
                    sb.append(msgs.get(k));
                    if (k < msgs.size() - 1) {
                        sb.append(" ");
                    }
                }
                System.out.println(sb.toString());
            }
        }
        
        scanner.close();
    }
}

Java 代码亮点

• 事件对象化：将不同类型的操作统一封装为 Event 对象，利用 Comparable 接口优雅地处理复杂的时间与类型排序逻辑。
• 优先级映射：巧妙地将题目要求的执行顺序（取消->订阅->发送）映射为整数 0, 1, 2，简化了比较逻辑。
• 集合操作：使用 HashSet 维护当前订阅者，利用 Stream 或简单循环快速查找最大 ID（最高优先级）。
• 健壮性：处理了空行、多余空格等输入格式问题。

---

四、Go 语言实现🚀

package main

import (
	"bufio"
	"fmt"
	"os"
	"sort"
	"strconv"
	"strings"
)

const (
	TypeCancel   = 0
	TypeSubscribe = 1
	TypeSend     = 2
)

type Event struct {
	Time     int
	Type     int
	Consumer int // -1 for message
	Content  int // 0 for sub/cancel
}

func main() {
	scanner := bufio.NewScanner(os.Stdin)
	
	if !scanner.Scan() {
		return
	}
	line1 := scanner.Text()
	
	if !scanner.Scan() {
		return
	}
	line2 := scanner.Text()

	msgParts := strings.Fields(line1)
	subParts := strings.Fields(line2)

	var events []Event

	// 解析消息
	for i := 0; i < len(msgParts); i += 2 {
		t, _ := strconv.Atoi(msgParts[i])
		c, _ := strconv.Atoi(msgParts[i+1])
		events = append(events, Event{Time: t, Type: TypeSend, Consumer: -1, Content: c})
	}

	// 解析消费者
	m := len(subParts) / 2
	for i := 0; i < m; i++ {
		subT, _ := strconv.Atoi(subParts[2*i])
		canT, _ := strconv.Atoi(subParts[2*i+1])
		
		events = append(events, Event{Time: subT, Type: TypeSubscribe, Consumer: i, Content: 0})
		events = append(events, Event{Time: canT, Type: TypeCancel, Consumer: i, Content: 0})
	}

	// 排序
	sort.Slice(events, func(i, j int) bool {
		if events[i].Time != events[j].Time {
			return events[i].Time < events[j].Time
		}
		if events[i].Type != events[j].Type {
			return events[i].Type < events[j].Type // 0 < 1 < 2
		}
		return events[i].Consumer < events[j].Consumer
	})

	// 模拟
	activeSubs := make(map[int]bool)
	received := make([][]int, m)
	for i := range received {
		received[i] = make([]int, 0)
	}

	for _, e := range events {
		if e.Type == TypeCancel {
			delete(activeSubs, e.Consumer)
		} else if e.Type == TypeSubscribe {
			activeSubs[e.Consumer] = true
		} else if e.Type == TypeSend {
			if len(activeSubs) > 0 {
				bestConsumer := -1
				for id := range activeSubs {
					if id > bestConsumer {
						bestConsumer = id
					}
				}
				received[bestConsumer] = append(received[bestConsumer], e.Content)
			}
		}
	}

	// 输出
	for i := 0; i < m; i++ {
		if len(received[i]) == 0 {
			fmt.Println("-1")
		} else {
			var sb strings.Builder
			for k, val := range received[i] {
				sb.WriteString(strconv.Itoa(val))
				if k < len(received[i])-1 {
					sb.WriteString(" ")
				}
			}
			fmt.Println(sb.String())
		}
	}
}

Go 代码亮点

• 切片排序：使用 sort.Slice 配合闭包，逻辑清晰且高效。
• Map 维护状态：利用 map[int]bool 快速管理订阅状态，查找最大 ID 时遍历 Map 即可（由于 M≤10 ，遍历开销忽略不计）。
• 字符串处理：strings.Fields 自动处理多个空格分隔的情况，比 split 更鲁棒。
• 高性能 IO：bufio.Scanner 确保在大输入下依然快速。

---

五、逻辑推演与避坑指南

示例 2 深度推演

输入：

5 64 11 64 9 97
9 11 4 9

解析：

• 消息：(5, 64), (11, 64), (9, 97)
• 消费者 0 (低优): 订阅@9, 取消@11
• 消费者 1 (高优): 订阅@4, 取消@9

事件列表构建与排序：

1. (4, SUB, C1) -> 时间4, 类型1
2. (5, SEND, 64) -> 时间5, 类型2
3. (9, CAN, C1) -> 时间9, 类型0 (关键点：类型0排最前)
4. (9, SUB, C0) -> 时间9, 类型1
5. (9, SEND, 97) -> 时间9, 类型2
6. (11, CAN, C0) -> 时间11, 类型0
7. (11, SEND, 64)-> 时间11, 类型2

执行流程：

1. t=4: C1 订阅。Active={1}
2. t=5: 发送 64。Active 非空，最高优是 C1。-> C1 收到 64。
3. t=9:
   • 先执行 CAN C1: Active 移除 1 -> Active={}
   • 再执行 SUB C0: Active 加入 0 -> Active={0}
   • 最后执行 SEND 97: Active 非空，最高优是 C0。-> C0 收到 97。
4. t=11:
   • 先执行 CAN C0: Active 移除 0 -> Active={}
   • 再执行 SEND 64: Active 为空。-> 消息丢弃。

最终输出：

• C0: 97
• C1: 64
  与题目示例输出完全一致。

⚠️ 常见坑点

1. 消息未排序：题目明确说“消息并没有按照发送时刻排列”，必须将所有事件放入列表统一排序，不能直接按输入顺序处理。
2. 同一时刻顺序：这是本题最大的陷阱。如果先处理消息再处理取消，会导致 t=9 时消息错误地发给 C1；如果先处理订阅再处理取消，逻辑也会错。必须严格遵守：取消 > 订阅 > 发送。
3. 优先级判断：输入是按优先级升序给的，意味着数组下标越大，优先级越高。很多考生容易搞反，误以为下标 0 优先级最高。
4. 空输出格式：如果没有收到消息，必须输出 -1，而不是空行。

---

六、复杂度分析📊

• 时间复杂度：
  • 事件总数 K=N+2M 。
  • 排序耗时 O(Klog⁡K) 。
  • 遍历处理耗时 O(K×M) （因为每次发送消息需要遍历最多 M 个用户找最大值）。
  • 鉴于 N≤100,M≤10 ，总运算量极小，毫秒级完成。
• 空间复杂度：
  • O(K) 存储事件列表。
  • O(N×M) 存储结果（最坏情况所有消息都被某个人接收）。

---

七、结语

“模拟消息队列”是一道考察逻辑思维严密性的经典题目。它不要求高深的算法，但要求对边界条件和执行时序有精准的把控。

• 核心技巧：将不同操作抽象为带优先级的“事件”，统一排序后线性扫描。
• 易错点：时刻相同时的操作顺序、优先级的方向。

掌握这种事件驱动的思维模式，不仅能解决此类机考题，对日后开发异步系统、定时任务调度等实际工程场景也大有裨益。祝大家刷题顺利，早日拿到 Offer！