用数组维护每个车位上的占用区间列表,再用哈希表记录 carId -> (spot, start, end)。
reserve:若该车已有预约或 start >= end 则失败;否则按车位编号从小到大,找第一个与 [start,end) 半开不相交(start < e && s < end 为相交)的车位分配。cancel / spotOf:查表删除或返回车位。busyCount:统计满足 start <= time < end 的预约数。调用量 ≤3000、n≤200,直接扫描区间即可。
请实现一个支持按时间段预约车位的停车场系统。
共有 n 个车位,编号 0,1,…,n−1,初始全部空闲。
一次预约用两个整数描述占用时段:
start:开始占用的时刻(含)end:结束占用的时刻(不含)即车辆占用半开区间 [start,end):从时刻 start 起占着车位,到时刻 end 起不再占用。因此:
每辆车在取消前最多保留一段有效预约;不同车辆占用同一车位的区间不得相交。
ParkingLot(int n):初始化 n 个空车位。reserve(int carId, int start, int end):为车辆 carId 预约时段 [start,end)。
-1-1cancel(int carId):取消该车当前预约。无预约返回 false,否则释放占用并返回 truespotOf(int carId):返回该车当前车位编号;无预约返回 -1busyCount(int time):返回在时刻 time 正在占用中的车辆数(start≤time<end)每行一次函数调用。首行 ParkingLot(n)。累计调用不超过 3000 次。
reserve 返回 -1)nullreserve / spotOf / busyCount 返回整数cancel 返回 true / false输入:
ParkingLot(2)
reserve(1, 0, 10)
reserve(2, 5, 15)
reserve(3, 0, 6)
busyCount(5)
cancel(1)
reserve(3, 0, 5)
spotOf(3)
busyCount(4)
reserve(2, 0, 1)
输出:
null
0
1
-1
2
true
0
0
1
-1
说明:
1 预约 [0,10),分到车位 02 预约 [5,15),与车位 0 冲突,分到车位 13 预约 [0,6):与车位 0 的 [0,10)、车位 1 的 [5,15) 都相交,失败返回 -1busyCount 为 21 后,车 3 可预约 [0,5) 到车位 0(与 [5,15) 在时刻 5 处「首尾相接」不相交)2 仍有预约,再次 reserve 失败
By signing up a CodeFun2000 universal account, you can submit code and join discussions in all online judging services provided by us.