题目描述与示例

题目描述

让我们来模拟一个消息队列的运作，有一个发布者和若干消费者，发布者会在给定的时刻向消息队列发送消息：

1. 若此时消息队列有消费者订阅，这个消息会被发送到订阅的消费者中优先级最高（输入中消费者按优先级升序排列）的一个；
2. 若此时没有订阅的消费者，该消息被消息队列丢弃。

消费者则会在给定的时刻订阅消息队列或取消订阅。

1. 当消息发送和订阅发生在同一时刻时，先处理订阅操作，即同一时刻订阅的消费者成为消息发送的候选。
2. 当消息发送和取消订阅发生在同一时刻时，先处理取消订阅操作，即消息不会被发送到同一时刻取消订阅的消费者。

题目练习网址：https://www.algomooc.com/problem/P2506

输入描述

输入为两行。

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

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

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

输出描述

输出为M行，依次为M个消费者收到的消息内容，消息内容按收到的顺序排列，且由空格分隔；

若某个消费者没有收到任何消息，则对应的行输出-1.

示例一

输入

2 22 1 11 4 44 5 55 3 33
1 7 2 3

输出

11 33 44 55
22

说明

消息11在1时刻到达，此时只有第一个消费者订阅，消息发送给它；

消息22在2时刻到达，此时两个消费者都订阅了，消息发送给优先级最高的第二个消费者；

消息33在3时刻到达，此时只有第一个消费者订阅，消息发送给它；

余下的消息按规则也是发送给第一个消费者。

示例二

输入

5 64 11 64 9 97
9 11 4 9

输出

97
64

说明

消息64在5时刻到达，此时只有第二个消费者订阅，消息发送给它；

消息97在9时刻到达，此时只有第一消费者订阅（因为第二个消费者刚好在9时刻取消订阅），消息发送给它；

11时刻也到达了一个内容为64的消息，不过因为没有消费者订阅，消息被丢弃。

解题思路

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

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

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

2 22 1 11 4 44 5 55 3 33

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

msg_lst = [[2, 22], [1, 11], [4, 44], [5, 55], [3, 33]]

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

msg_lst.sort()

可以得到结果

msg_lst = [[1, 11], [2, 22], [3, 33], [4, 44], [5, 55]]

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

1 7 2 3

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

person_lst = [[1, 7], [2, 3]]

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

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

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

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

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

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

整理为代码即

ans = [list() for _ in range(m)]

for msg_time, msg in msg_lst:
    for i in range(m-1, -1, -1):
        start, end = person_lst[i]
        if start <= msg_time < end:
            ans[i].append(str(msg))
            break

代码

Python

# 欢迎来到「欧弟算法 - 华为OD全攻略」,收录华为OD题库、面试指南、八股文与学员案例！
# 地址：https://www.odalgo.com
# 华为OD机试刷题网站：https://www.algomooc.com
# 添加微信 278166530 获取华为 OD 笔试真题题库和视频


# 输入所有消息的信息
lst = list(map(int, input().split()))
# 将长度为2n的一维列表lst转化为n*2的二维列表msg_lst
# msg_lst[i][0]表示第i个消息发送的时刻，msg_lst[i][1]表示第i个消息的信息
msg_lst = [(lst[i], lst[i+1]) for i in range(0, len(lst), 2)]
# 消息列表根据消息发送时间进行排序
msg_lst.sort()

# 获得消息数目n
n = len(msg_lst)

# 输入所有订阅者的信息
lst = list(map(int, input().split()))
# 将长度为2m的一维列表lst转化为m*2的二维列表person_lst
# person_lst[i][0]表示第i个订阅者的开始订阅时间，msg_lst[i][1]表示第i个订阅者的取消订阅时间
person_lst = [(lst[i], lst[i+1]) for i in range(0, len(lst), 2)]
# 获得订阅者人数m
m = len(person_lst)

# 构建长度为m的二维答案数组，用以储存每一个订阅者的推送情况
# 这里用defaultdict(list)也是没有问题的
ans = [list() for _ in range(m)]


# 对已经按照时间顺序排列的msg_lst进行遍历
# msg_time, msg分别为推送时间和信息内容
for msg_time, msg in msg_lst:
    # 根据优先级顺序遍历订阅者，优先级越高的订阅者排在越后的位置
    # 故逆序遍历person_lst列表
    for i in range(m-1, -1, -1):
        # 获得第i个订阅者开始订阅和取消订阅的时间
        start, end = person_lst[i]
        # 如果当前消息的发送时间位于[start, end)之间
        # 即被第i个订阅者订阅，那么推送给这个订阅者
        # 在ans列表中加入msg的内容
        # 同时由于只需要推送给优先级高的订阅者，所以无需继续遍历，直接退出循环
        if start <= msg_time < end:
            ans[i].append(str(msg))
            break


# 遍历每一个订阅者的订阅情况
for item in ans:
    # 如果该订阅者没有收到任何订阅消息，输出-1
    if len(item) == 0:
        print(-1)
    # 否则输出用字符串的形式输出订阅消息
    else:
        print(" ".join(item))

Java

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);

        // 输入消息列表
        List<int[]> msgList = new ArrayList<>();
        String[] msgData = scanner.nextLine().split(" ");
        for (int i = 0; i < msgData.length; i += 2) {
            int msgTime = Integer.parseInt(msgData[i]);
            int msgContent = Integer.parseInt(msgData[i + 1]);
            msgList.add(new int[]{msgTime, msgContent});
        }
        // 按照消息时间进行排序
        msgList.sort(Comparator.comparingInt(a -> a[0]));

        // 输入订阅者信息
        List<int[]> personList = new ArrayList<>();
        String[] personData = scanner.nextLine().split(" ");
        for (int i = 0; i < personData.length; i += 2) {
            int start = Integer.parseInt(personData[i]);
            int end = Integer.parseInt(personData[i + 1]);
            personList.add(new int[]{start, end});
        }
        
        // 构建二维列表，存储每个订阅者的消息
        List<List<String>> ans = new ArrayList<>();
        for (int i = 0; i < personList.size(); i++) {
            ans.add(new ArrayList<>());
        }

        // 遍历已排序的消息列表
        for (int[] msg : msgList) {
            int msgTime = msg[0];
            String msgContent = Integer.toString(msg[1]);

            // 逆序遍历订阅者，优先级越高的订阅者排在越后的位置
            for (int i = personList.size() - 1; i >= 0; i--) {
                int start = personList.get(i)[0];
                int end = personList.get(i)[1];

                if (start <= msgTime && msgTime < end) {
                    ans.get(i).add(msgContent);
                    break;
                }
            }
        }

        // 输出结果
        for (List<String> messages : ans) {
            if (messages.isEmpty()) {
                System.out.println(-1);
            } else {
                System.out.println(String.join(" ", messages));
            }
        }
    }
}

C++

#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <sstream>

using namespace std;

int main() {
    // 输入消息列表
    vector<pair<int, int>> msgList;
    string line;
    getline(cin, line);
    stringstream msgStream(line);
    int msgTime, msgContent;
    
    while (msgStream >> msgTime >> msgContent) {
        msgList.push_back({msgTime, msgContent});
    }
    // 按照消息发送时间进行排序
    sort(msgList.begin(), msgList.end());

    // 输入订阅者信息
    vector<pair<int, int>> personList;
    getline(cin, line);
    stringstream personStream(line);
    int start, end;
    
    while (personStream >> start >> end) {
        personList.push_back({start, end});
    }
    
    int m = personList.size();
    vector<vector<string>> ans(m);

    // 遍历已排序的消息列表
    for (auto& msg : msgList) {
        int msgTime = msg.first;
        string msgContent = to_string(msg.second);

        // 逆序遍历订阅者列表
        for (int i = m - 1; i >= 0; --i) {
            int start = personList[i].first;
            int end = personList[i].second;

            if (start <= msgTime && msgTime < end) {
                ans[i].push_back(msgContent);
                break;
            }
        }
    }

    // 输出结果
    for (auto& messages : ans) {
        if (messages.empty()) {
            cout << -1 << endl;
        } else {
            for (size_t j = 0; j < messages.size(); ++j) {
                cout << messages[j];
                if (j < messages.size() - 1) {
                    cout << " ";
                }
            }
            cout << endl;
        }
    }

    return 0;
}

C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define MAX_MSG 100
#define MAX_PERSON 100
#define MAX_LEN 1000

// 定义消息结构体
typedef struct {
    int time;   // 消息发送时间
    int info;   // 消息内容
} Message;

// 定义订阅者结构体
typedef struct {
    int start;  // 订阅开始时间
    int end;    // 订阅结束时间
} Subscriber;

// 比较函数，用于对消息按发送时间排序
int compareMessages(const void *a, const void *b) {
    return ((Message *)a)->time - ((Message *)b)->time;
}

int main() {
    char line[MAX_LEN];
    Message messages[MAX_MSG];
    Subscriber subscribers[MAX_PERSON];
    int m = 0, n = 0;
    int ans[MAX_PERSON][MAX_MSG];  // 存储每个订阅者收到的消息
    int ans_count[MAX_PERSON] = {0};  // 每个订阅者收到的消息数目

    // 输入所有消息的信息
    fgets(line, sizeof(line), stdin);
    char *token = strtok(line, " ");
    while (token) {
        int time = atoi(token);
        token = strtok(NULL, " ");
        int info = atoi(token);
        token = strtok(NULL, " ");
        messages[m].time = time;
        messages[m].info = info;
        m++;
    }

    // 按消息时间排序
    qsort(messages, m, sizeof(Message), compareMessages);

    // 输入所有订阅者的信息
    fgets(line, sizeof(line), stdin);
    token = strtok(line, " ");
    while (token) {
        int start = atoi(token);
        token = strtok(NULL, " ");
        int end = atoi(token);
        token = strtok(NULL, " ");
        subscribers[n].start = start;
        subscribers[n].end = end;
        n++;
    }

    // 遍历消息列表并推送给订阅者
    for (int i = 0; i < m; i++) {
        int msg_time = messages[i].time;
        int msg_info = messages[i].info;

        // 遍历订阅者列表，优先级从后往前遍历
        for (int j = n - 1; j >= 0; j--) {
            int start = subscribers[j].start;
            int end = subscribers[j].end;

            // 如果当前消息在订阅范围内，推送给该订阅者
            if (msg_time >= start && msg_time < end) {
                ans[j][ans_count[j]++] = msg_info;
                break;  // 已推送给优先级最高的订阅者，退出循环
            }
        }
    }

    // 输出每个订阅者的订阅消息
    for (int i = 0; i < n; i++) {
        if (ans_count[i] == 0) {
            printf("-1\n");  // 该订阅者没有收到任何消息
        } else {
            for (int j = 0; j < ans_count[i]; j++) {
                printf("%d", ans[i][j]);
                if (j < ans_count[i] - 1) printf(" ");
            }
            printf("\n");
        }
    }

    return 0;
}

Node JavaScript

const readline = require('readline');
const rl = readline.createInterface({
    input: process.stdin,
    output: process.stdout
});

// 处理输入数据
rl.question('', (input1) => {
    const lst1 = input1.split(' ').map(Number);
    const msg_lst = [];
    for (let i = 0; i < lst1.length; i += 2) {
        msg_lst.push([lst1[i], lst1[i + 1]]);
    }
    // 按消息发送时间排序
    msg_lst.sort((a, b) => a[0] - b[0]);

    rl.question('', (input2) => {
        const lst2 = input2.split(' ').map(Number);
        const person_lst = [];
        for (let i = 0; i < lst2.length; i += 2) {
            person_lst.push([lst2[i], lst2[i + 1]]);
        }

        // 初始化每个订阅者的推送情况
        const ans = Array.from({ length: person_lst.length }, () => []);

        // 遍历消息列表并推送到订阅者
        for (const [msg_time, msg] of msg_lst) {
            for (let i = person_lst.length - 1; i >= 0; i--) {
                const [start, end] = person_lst[i];
                if (start <= msg_time && msg_time < end) {
                    ans[i].push(msg.toString());
                    break;
                }
            }
        }

        // 输出结果
        ans.forEach((item) => {
            if (item.length === 0) {
                console.log(-1);
            } else {
                console.log(item.join(' '));
            }
        });

        rl.close();
    });
});

Go

package main

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

// 定义消息和订阅者结构体
type Message struct {
    time int
    info int
}

type Subscriber struct {
    start int
    end   int
}

func main() {
    reader := bufio.NewReader(os.Stdin)

    // 输入消息数据
    input1, _ := reader.ReadString('\n')
    lst1 := strings.Fields(input1)
    var msg_lst []Message
    for i := 0; i < len(lst1); i += 2 {
        time, _ := strconv.Atoi(lst1[i])
        info, _ := strconv.Atoi(lst1[i+1])
        msg_lst = append(msg_lst, Message{time: time, info: info})
    }

    // 按消息时间排序
    sort.Slice(msg_lst, func(i, j int) bool {
        return msg_lst[i].time < msg_lst[j].time
    })

    // 输入订阅者数据
    input2, _ := reader.ReadString('\n')
    lst2 := strings.Fields(input2)
    var person_lst []Subscriber
    for i := 0; i < len(lst2); i += 2 {
        start, _ := strconv.Atoi(lst2[i])
        end, _ := strconv.Atoi(lst2[i+1])
        person_lst = append(person_lst, Subscriber{start: start, end: end})
    }

    // 初始化每个订阅者的推送情况
    ans := make([][]string, len(person_lst))
    for i := range ans {
        ans[i] = []string{}
    }

    // 遍历消息并推送到订阅者
    for _, msg := range msg_lst {
        for i := len(person_lst) - 1; i >= 0; i-- {
            start, end := person_lst[i].start, person_lst[i].end
            if start <= msg.time && msg.time < end {
                ans[i] = append(ans[i], strconv.Itoa(msg.info))
                break
            }
        }
    }

    // 输出结果
    writer := bufio.NewWriter(os.Stdout)
    defer writer.Flush()
    for _, item := range ans {
        if len(item) == 0 {
            fmt.Fprintln(writer, -1)
        } else {
            fmt.Fprintln(writer, strings.Join(item, " "))
        }
    }
}

时空复杂度

时间复杂度：O(``N*M+NlogN``)。需要遍历N条消息，每一条消息都要逆序遍历M个订阅者。对N条消息进行排序的时间复杂度为O(NlogN)。

空间复杂度：O(``N+M``)。