题目
会议接待
某公司需要安排会议室接待客户，每个会议室在一天的不同时间段有不同的预约情况。你需要根据预约情况，找到一个满足以下条件的会议室：
- 会议室的容量大于等于所需的容量。
- 在指定的时间段内，会议室没有被预约。
输入
输入包含多个测试用例，每个测试用例描述如下：
- 第一行包含两个整数 n 和 m，分别表示会议室的数量和查询的数量。
- 接下来的 n 行，每行描述一个会议室的容量和预约情况：
- 第一个整数 cap 表示会议室的容量。
- 第二个整数 k 表示该会议室在一天中的预约数量。
- 接下来的 k 行，每行包含两个整数 start 和 end，表示预约的开始时间和结束时间（单位：分钟）。
- 接下来的 m 行，每行描述一个查询：
- 第一个整数 need_cap 表示所需的容量。
- 第二个整数 query_start 和第三个整数 query_end 表示查询的时间段（单位：分钟）。
输出
对于每个查询，输出满足条件的会议室编号（从1开始编号）。如果有多个会议室满足条件，输出编号最小的那个。如果没有会议室满足条件，输出 -1。
示例
输入
3 3
10 2
0 60
120 180
15 1
30 90
20 2
0 30
60 120
5 0 60
10 30 90
15 60 120
输出
1
2
-1
思路
- 预处理会议室的预约情况：对于每个会议室，我们需要预处理其预约的时间段，以便快速判断某个时间段是否可用。
- 查询处理：对于每个查询，遍历所有会议室，检查每个会议室在指定时间段内是否有预约，同时检查容量是否满足要求。
为了实现快速的时间段查询，可以使用线段树、树状数组或扫描线等数据结构，但考虑到题目给定的时间范围和数据量，直接遍历每个会议室的预约情况并检查是否冲突也是一种可行的方法。
Java 解析
import java.util.*;
class MeetingRoom {
int cap;
List<int[]> bookings;
MeetingRoom(int cap, int k) {
this.cap = cap;
this.bookings = new ArrayList<>();
for (int i = 0; i < k; i++) {
int start = scanner.nextInt();
int end = scanner.nextInt();
bookings.add(new int[]{start, end});
}
}
boolean isAvailable(int start, int end) {
for (int[] booking : bookings) {
if (start < booking[1] && end > booking[0]) {
return false;
}
}
return true;
}
}
public class Main {
static Scanner scanner = new Scanner(System.in);
public static void main(String[] args) {
int n = scanner.nextInt();
int m = scanner.nextInt();
MeetingRoom[] rooms = new MeetingRoom[n];
for (int i = 0; i < n; i++) {
int cap = scanner.nextInt();
int k = scanner.nextInt();
rooms[i] = new MeetingRoom(cap, k);
}
for (int i = 0; i < m; i++) {
int needCap = scanner.nextInt();
int queryStart = scanner.nextInt();
int queryEnd = scanner.nextInt();
int result = -1;
for (int j = 0; j < n; j++) {
if (rooms[j].cap >= needCap && rooms[j].isAvailable(queryStart, queryEnd)) {
result = j + 1;
break;
}
}
System.out.println(result);
}
}
}
C++ 解析
#include <iostream>
#include <vector>
using namespace std;
struct MeetingRoom {
int cap;
vector<pair<int, int>> bookings;
MeetingRoom(int cap, int k) : cap(cap) {}
bool isAvailable(int start, int end) {
for (const auto& booking : bookings) {
if (start < booking.second && end > booking.first) {
return false;
}
}
return true;
}
};
int main() {
int n, m;
cin >> n >> m;
vector<MeetingRoom> rooms(n);
for (int i = 0; i < n; ++i) {
int cap, k;
cin >> cap >> k;
rooms[i] = MeetingRoom(cap, k);
for (int j = 0; j < k; ++j) {
int start, end;
cin >> start >> end;
rooms[i].bookings.emplace_back(start, end);
}
}
for (int i = 0; i < m; ++i) {
int needCap, queryStart, queryEnd;
cin >> needCap >> queryStart >> queryEnd;
int result = -1;
for (int j = 0; j < n; ++j) {
if (rooms[j].cap >= needCap && rooms[j].isAvailable(queryStart, queryEnd)) {
result = j + 1;
break;
}
}
cout << result << endl;
}
return 0;
}
Python 解析
class MeetingRoom:
def __init__(self, cap, k):
self.cap = cap
self.bookings = []
for _ in range(k):
start, end = map(int, input().split())
self.bookings.append((start, end))
def is_available(self, start, end):
for booking in self.bookings:
if start < booking[1] and end > booking[0]:
return False
return True
if __name__ == "__main__":
import sys
input = sys.stdin.read
data = input().split()
index = 0
n = int(data[index])
index += 1
m = int(data[index])
index += 1
rooms = []
for _ in range(n):
cap = int(data[index])
index += 1
k = int(data[index])
index += 1
room = MeetingRoom(cap, k)
rooms.append(room)
for _ in range(k):
index += 2 # Skip the start and end times read by MeetingRoom constructor
results = []
for _ in range(m):
need_cap = int(data[index])
index += 1
query_start = int(data[index])
index += 1
query_end = int(data[index])
index += 1
result = -1
for room in rooms:
if room.cap >= need_cap and room.is_available(query_start, query_end):
result = rooms.index(room) + 1
break
results.append(result)
for result in results:
print(result)
 | 学习笔记)
