座位预约管理系统

1845. 座位预约管理系统

请你设计一个管理 n 个座位预约的系统，座位编号从 1 到 n 。

请你实现 SeatManager 类：

SeatManager(int n) 初始化一个 SeatManager 对象，它管理从 1 到 n 编号的 n 个座位。所有座位初始都是可预约的。
int reserve() 返回可以预约座位的 最小编号 ，此座位变为不可预约。
void unreserve(int seatNumber) 将给定编号 seatNumber 对应的座位变成可以预约。

示例 1：

输入：
["SeatManager", "reserve", "reserve", "unreserve", "reserve", "reserve", "reserve", "reserve", "unreserve"]
[[5], [], [], [2], [], [], [], [], [5]]
输出：
[null, 1, 2, null, 2, 3, 4, 5, null]

解释：
SeatManager seatManager = new SeatManager(5); // 初始化 SeatManager ，有 5 个座位。
seatManager.reserve();    // 所有座位都可以预约，所以返回最小编号的座位，也就是 1 。
seatManager.reserve();    // 可以预约的座位为 [2,3,4,5] ，返回最小编号的座位，也就是 2 。
seatManager.unreserve(2); // 将座位 2 变为可以预约，现在可预约的座位为 [2,3,4,5] 。
seatManager.reserve();    // 可以预约的座位为 [2,3,4,5] ，返回最小编号的座位，也就是 2 。
seatManager.reserve();    // 可以预约的座位为 [3,4,5] ，返回最小编号的座位，也就是 3 。
seatManager.reserve();    // 可以预约的座位为 [4,5] ，返回最小编号的座位，也就是 4 。
seatManager.reserve();    // 唯一可以预约的是座位 5 ，所以返回 5 。
seatManager.unreserve(5); // 将座位 5 变为可以预约，现在可预约的座位为 [5] 。

提示：

1 <= n <= 10⁵
1 <= seatNumber <= n
每一次对 reserve 的调用，题目保证至少存在一个可以预约的座位。
每一次对 unreserve 的调用，题目保证 seatNumber 在调用函数前都是被预约状态。
对 reserve 和 unreserve 的调用总共不超过 10⁵ 次。

原站题解

去查看

上次编辑到这里，代码来自缓存点击恢复默认模板

class SeatManager { public: SeatManager(int n) { } int reserve() { } void unreserve(int seatNumber) { } }; /** * Your SeatManager object will be instantiated and called as such: * SeatManager* obj = new SeatManager(n); * int param_1 = obj->reserve(); * obj->unreserve(seatNumber); */

rust 解法, 执行用时: 70 ms, 内存消耗: 27.4 MB, 提交时间: 2024-09-30 08:07:22

use std::collections::BinaryHeap;

struct SeatManager {
    available: BinaryHeap<i32>,
}

impl SeatManager {
    fn new(n: i32) -> Self {
        let mut available = BinaryHeap::new();
        for i in 1..=n {
            available.push(-i); // 取相反数，变成最小堆
        }
        Self { available }
    }

    fn reserve(&mut self) -> i32 {
        -self.available.pop().unwrap()
    }

    fn unreserve(&mut self, seat_number: i32) {
        self.available.push(-seat_number);
    }
}


/**
 * Your SeatManager object will be instantiated and called as such:
 * let obj = SeatManager::new(n);
 * let ret_1: i32 = obj.reserve();
 * obj.unreserve(seatNumber);
 */

rust 解法, 执行用时: 71 ms, 内存消耗: 27.4 MB, 提交时间: 2024-09-30 08:06:59

use std::collections::BinaryHeap;

struct SeatManager {
    seats: i32,
    available: BinaryHeap<i32>,
}

impl SeatManager {
    fn new(_: i32) -> Self {
        Self { seats: 0, available: BinaryHeap::new() }
    }

    fn reserve(&mut self) -> i32 {
        if let Some(seat) = self.available.pop() { // 有空出来的椅子
            -seat // 坐编号最小的
        } else {
            self.seats += 1; // 添加一把新的椅子
            self.seats
        }
    }

    fn unreserve(&mut self, seat_number: i32) {
        self.available.push(-seat_number); // 有人离开了椅子
    }
}


/**
 * Your SeatManager object will be instantiated and called as such:
 * let obj = SeatManager::new(n);
 * let ret_1: i32 = obj.reserve();
 * obj.unreserve(seatNumber);
 */

javascript 解法, 执行用时: 537 ms, 内存消耗: 93 MB, 提交时间: 2024-09-30 08:06:36

var SeatManager = function(_) {
    this.seats = 0; // 一开始没有椅子
    this.available = new MinPriorityQueue();
};

SeatManager.prototype.reserve = function() {
    if (!this.available.isEmpty()) { // 有空出来的椅子
        return this.available.dequeue().element; // 坐编号最小的
    }
    return ++this.seats; // 添加一把新的椅子
};

SeatManager.prototype.unreserve = function(seatNumber) {
    this.available.enqueue(seatNumber); // 有人离开了椅子
};


/**
 * Your SeatManager object will be instantiated and called as such:
 * var obj = new SeatManager(n)
 * var param_1 = obj.reserve()
 * obj.unreserve(seatNumber)
 */

javascript 解法, 执行用时: 729 ms, 内存消耗: 92.8 MB, 提交时间: 2024-09-30 08:06:09

var SeatManager = function(n) {
    this.available = new MinPriorityQueue();
    for (let i = 1; i <= n; i++) {
        this.available.enqueue(i);
    }
};

SeatManager.prototype.reserve = function() {
    return this.available.dequeue().element;
};

SeatManager.prototype.unreserve = function(seatNumber) {
    this.available.enqueue(seatNumber);
};



/**
 * Your SeatManager object will be instantiated and called as such:
 * var obj = new SeatManager(n)
 * var param_1 = obj.reserve()
 * obj.unreserve(seatNumber)
 */

php 解法, 执行用时: 372 ms, 内存消耗: 65.4 MB, 提交时间: 2023-09-11 15:25:32

class SeatManager {
    /**
     * @param Integer $n
     */
    function __construct($n) {
        $this->queue = new \SplPriorityQueue();
        $this->n = $n;
        for ($i = 0; $i < $n; $i++ ) {
            $this->queue->insert($i + 1, $n - $i);
        }
    }

    /**
     * @return Integer
     */
    function reserve() {
        $ans = $this->queue->top();
        $this->queue->extract();
        return $ans;
    }

    /**
     * @param Integer $seatNumber
     * @return NULL
     */
    function unreserve($seatNumber) {
        $this->queue->insert($seatNumber, $this->n - $seatNumber + 1);
    }
}

/**
 * Your SeatManager object will be instantiated and called as such:
 * $obj = SeatManager($n);
 * $ret_1 = $obj->reserve();
 * $obj->unreserve($seatNumber);
 */

golang 解法, 执行用时: 308 ms, 内存消耗: 30 MB, 提交时间: 2023-09-11 15:14:01

// 小根堆
type SeatManager struct {
    sort.IntSlice
}

func Constructor(n int) SeatManager {
    sm := SeatManager{}
    for i:=1;i<=n;i++{
        heap.Push(&sm, i)
    }
    return sm
}

func (this *SeatManager) Reserve() int {
    v := heap.Pop(this)
    return v.(int)
}

func (this *SeatManager) Unreserve(seatNumber int)  {
    heap.Push(this, seatNumber)
}

func (this *SeatManager) Push(x interface{}) {
    this.IntSlice = append(this.IntSlice, x.(int))
}

func (this *SeatManager) Pop() interface{}{
    v := this.IntSlice[this.Len()-1]
    this.IntSlice = this.IntSlice[:this.Len()-1]
    return v
}


/**
 * Your SeatManager object will be instantiated and called as such:
 * obj := Constructor(n);
 * param_1 := obj.Reserve();
 * obj.Unreserve(seatNumber);
 */

golang 解法, 执行用时: 476 ms, 内存消耗: 30.6 MB, 提交时间: 2023-09-11 15:13:10

type SeatManager struct {
    seats []bool
    tmp []int
    min int
}


func Constructor(n int) SeatManager {
    helper := make([]bool, n + 1)
    return SeatManager{seats: helper, tmp: []int{}, min: 1}
}


func (this *SeatManager) Reserve() int {
    if len(this.tmp) != 0{
        sort.Slice(this.tmp, func(i, j int)bool{
            return this.tmp[i] < this.tmp[j]
        })
        res := this.tmp[0]
        this.seats[res] = false
        this.tmp = this.tmp[1:]
        return res
    }else{
        this.seats[this.min] = false
        res := this.min
        this.min++
        return res
    }
}


func (this *SeatManager) Unreserve(seatNumber int)  {
    this.tmp = append(this.tmp, seatNumber)
    this.seats[seatNumber] = true
}


/**
 * Your SeatManager object will be instantiated and called as such:
 * obj := Constructor(n);
 * param_1 := obj.Reserve();
 * obj.Unreserve(seatNumber);
 */

java 解法, 执行用时: 40 ms, 内存消耗: 89.6 MB, 提交时间: 2023-09-11 15:12:05

class SeatManager {
    PriorityQueue<Integer> queue;
    int i=1;
    public SeatManager(int n) {
        queue=new PriorityQueue<>();      
    }
    public int reserve() {
        if(!queue.isEmpty()) return queue.poll();
        else return i++;            
    }
    public void unreserve(int seatNumber) {
        queue.add(seatNumber);
    }
}

/**
 * Your SeatManager object will be instantiated and called as such:
 * SeatManager obj = new SeatManager(n);
 * int param_1 = obj.reserve();
 * obj.unreserve(seatNumber);
 */

cpp 解法, 执行用时: 468 ms, 内存消耗: 144.1 MB, 提交时间: 2023-09-11 15:11:35

// 优先队列
class SeatManager {
    priority_queue<int,vector<int>, greater<int>> q;
public:
    SeatManager(int n) {
        for (size_t i = 0; i < n; i++)
            q.push(i + 1);
    }

    int reserve() {
        auto ans = q.top();
        q.pop();
        return ans;
    }

    void unreserve(int seatNumber) {
        q.push(seatNumber);
    }
};

/**
 * Your SeatManager object will be instantiated and called as such:
 * SeatManager* obj = new SeatManager(n);
 * int param_1 = obj->reserve();
 * obj->unreserve(seatNumber);
 */

cpp 解法, 执行用时: 356 ms, 内存消耗: 144.2 MB, 提交时间: 2023-09-11 15:11:11

class SeatManager {
public:
    vector<int> available;

    SeatManager(int n) {
        for (int i = 1; i <= n; ++i){
            available.push_back(i);
        }
    }
    
    int reserve() {
        pop_heap(available.begin(), available.end(), greater<int>());
        int tmp = available.back();
        available.pop_back();
        return tmp;
    }
    
    void unreserve(int seatNumber) {
        available.push_back(seatNumber);
        push_heap(available.begin(), available.end(), greater<int>());
    }
};

/**
 * Your SeatManager object will be instantiated and called as such:
 * SeatManager* obj = new SeatManager(n);
 * int param_1 = obj->reserve();
 * obj->unreserve(seatNumber);
 */

python3 解法, 执行用时: 512 ms, 内存消耗: 44.5 MB, 提交时间: 2023-09-11 15:10:47

# 最小堆
from heapq import heappush, heappop

class SeatManager:

    def __init__(self, n: int):
        self.available = list(range(1, n + 1))

    def reserve(self) -> int:
        return heappop(self.available)

    def unreserve(self, seatNumber: int) -> None:
        heappush(self.available, seatNumber)


# Your SeatManager object will be instantiated and called as such:
# obj = SeatManager(n)
# param_1 = obj.reserve()
# obj.unreserve(seatNumber)

上一题

下一题

详情