会议室预约系统优化（蓝桥杯）

文章目录

• 会议室预约系统优化
• • 问题描述
  • 差分

会议室预约系统优化

问题描述

假设你是一家大型企业的 IT 工程师，企业内有

n 个会议室，每天都有多个部门预约会议室进行会议。你的任务是优化现有的会议室预约系统。

你需要设计一个程序来支持以下两种操作：

1. 预约会议室: 给定一个时间范围 [start,end] 和一个会议室的 ID ，预约该会议室在这个时间范围内。
2. 查询会议室状态: 给定一个时间点 t 和一个会议室的 ID，返回该会议室在时间点 t 的预约状态，即在这个时间点，该会议室正在被预约多少次。

输入格式
第一行包含一个整数 n，表示会议室的数量。

第二行包含一个整数 q，表示操作的数量。

接下来 q 行，每行描述一个操作。

如果是预约操作，则格式为：BOOK starttime endtime roomid。

如果是查询操作，则格式为：QUERY t roomid。

输出格式
对于每一个 QUERY 操作，输出一个整数，表示到时间点 t 为止，该会议室被预约了多少次。

样例输入

3
5
BOOK 10 20 0
BOOK 15 25 1
BOOK 20 30 0
QUERY 15 0
QUERY 25 1

样例输出

1
0

这里蓝桥官方给的样例好像是错的，应该为：

1
1

评测数据范围
1≤n≤10⁵，1≤q≤10⁵ ，0≤starttime<endtime≤10⁹ ， 0≤t≤10⁹ 。

差分

#include<bits/stdc++.h>
using namespace std;

int main()
{
    int n,q; // n是会议室的数量，q是操作的数量。
    scanf("%d %d",&n,&q); // 读取n和q的值。
    vector<map<int,int>> a(n); // 创建一个向量a，包含n个map，每个map用于存储每个会议室的预约开始时间和结束时间的差分。

    while(q--) // 遍历q次操作。
    {
        string s;
        cin>>s; // 读取操作的类型，BOOK或QUERY。
        if(s=="BOOK")
        {
            int l,r,id; // l为预约开始时间，r为预约结束时间，id为会议室的ID。
            scanf("%d %d %d",&l,&r,&id); // 读取这三个值。
            a[id][l]+=1; // 在预约开始时间，增加一个预约。
            a[id][r+1]-=1; // 在预约结束时间的下一时刻，减少一个预约。
        }
        else
        {
            int t,id; // t是查询的时间点，id是会议室的ID。
            scanf("%d %d",&t,&id); // 读取这两个值。
            int cnt=0; // cnt用于统计到时间点t，该会议室的预约总次数。
            for(auto i : a[id]) // 遍历id会议室的所有预约记录。
            {
                if(i.first > t) break; // 如果记录的时间点大于查询时间点t，则结束循环。
                cnt += i.second; // 累加每个有效时间点的预约差分值。
            }
            printf("%d\n",cnt); // 输出到时间点t，会议室id的预约总次数。
        }
    }
    return 0;
}

这个代码使用了一种称作"差分数组"的技术来高效管理会议室预约的增加和减少。通过在预约开始时增加计数，在预约结束后的下一时刻减少计数，这样就可以通过累加到任何给定时间点的差分值来计算该时间点的总预约次数。这种方法的优点是更新预约状态的操作时间复杂度为O(1)，查询操作的时间复杂度为O(m)，其中m是对应会议室的预约记录条数，这在大多数情况下要优于直接遍历每个预约记录来计算总预约次数。