座位预约管理系统
难度:
标签:
题目描述
代码结果
运行时间: 328 ms, 内存: 43.6 MB
/*
* This Java solution also uses a PriorityQueue but with more functional programming aspects.
* Since PriorityQueue doesn't have direct stream manipulation, the code retains the same logic
* but shows how functional-style comments could apply if operations were stream-capable.
* For example, adding seats in the constructor can be seen as a map operation.
*/
import java.util.PriorityQueue;
public class SeatManager {
private PriorityQueue<Integer> availableSeats;
public SeatManager(int n) {
availableSeats = new PriorityQueue<>();
// Stream-like initialization (not actual streams)
for (int i = 1; i <= n; i++) {
availableSeats.add(i);
}
}
public int reserve() {
return availableSeats.poll();
}
public void unreserve(int seatNumber) {
availableSeats.add(seatNumber);
}
}
解释
方法:
该题解通过使用最小堆(由Python的heapq库提供)来管理所有已释放的座位编号。对于未释放的座位,通过一个变量minV跟踪下一个可预约的最小座位编号。当调用reserve()时,如果堆中有已释放的座位,它将返回并弹出堆中的最小元素,即最小编号的座位;如果堆为空,则返回minV当前值,并将minV增加1。当调用unreserve(seatNumber)时,将座位号seatNumber添加到堆中,以便该座位号在将来被重新预约。
时间复杂度:
O(log n)
空间复杂度:
O(n)
代码细节讲解
🦆
在`SeatManager`类的实现中,为什么选择使用最小堆来维护已释放的座位编号,而不是其他数据结构如数组或链表?
▷🦆
如果连续调用`unreserve`方法将同一个座位编号加入最小堆多次,这会对`reserve`方法的输出产生什么影响?是否有处理重复座位编号的机制?
▷🦆
在`reserve`方法中,如果最小堆不为空,直接从堆中弹出最小元素。这种做法是否保证了每次都能返回最小的可预约的座位编号?
▷🦆
在`unreserve`方法中,将座位号加入最小堆而不做任何额外的检查。在实际应用中,是否需要考虑对座位的有效性(如编号是否在1到n之间)进行验证?
▷