-
Notifications
You must be signed in to change notification settings - Fork 1
Expand file tree
/
Copy pathSeatReservationManager.py
More file actions
135 lines (110 loc) · 4.08 KB
/
Copy pathSeatReservationManager.py
File metadata and controls
135 lines (110 loc) · 4.08 KB
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
"""
https://leetcode.com/problems/seat-reservation-manager/description/?envType=daily-question&envId=2023-11-06
Design a system that manages the reservation state of n seats that are numbered from 1 to n.
Implement the SeatManager class:
SeatManager(int n) Initializes a SeatManager object that will manage n seats numbered from 1 to n. All seats are initially available.
int reserve() Fetches the smallest-numbered unreserved seat, reserves it, and returns its number.
void unreserve(int seatNumber) Unreserves the seat with the given seatNumber.
Example 1:
Input
["SeatManager", "reserve", "reserve", "unreserve", "reserve", "reserve", "reserve", "reserve", "unreserve"]
[[5], [], [], [2], [], [], [], [], [5]]
Output
[null, 1, 2, null, 2, 3, 4, 5, null]
Explanation
SeatManager seatManager = new SeatManager(5); // Initializes a SeatManager with 5 seats.
seatManager.reserve(); // All seats are available, so return the lowest numbered seat, which is 1.
seatManager.reserve(); // The available seats are [2,3,4,5], so return the lowest of them, which is 2.
seatManager.unreserve(2); // Unreserve seat 2, so now the available seats are [2,3,4,5].
seatManager.reserve(); // The available seats are [2,3,4,5], so return the lowest of them, which is 2.
seatManager.reserve(); // The available seats are [3,4,5], so return the lowest of them, which is 3.
seatManager.reserve(); // The available seats are [4,5], so return the lowest of them, which is 4.
seatManager.reserve(); // The only available seat is seat 5, so return 5.
seatManager.unreserve(5); // Unreserve seat 5, so now the available seats are [5].
Constraints:
1 <= n <= 105
1 <= seatNumber <= n
For each call to reserve, it is guaranteed that there will be at least one unreserved seat.
For each call to unreserve, it is guaranteed that seatNumber will be reserved.
At most 105 calls in total will be made to reserve and unreserve.
"""
import heapq
from sortedcontainers import SortedSet
from Common.Constants import null
from Common.ObjectTestingUtils import run_object_tests
# Runtime
# Details
# 450ms
# Beats 50.00%of users with Python3
# Memory
# Details
# 43.98MB
# Beats 67.29%of users with Python3
# class SeatManager:
#
# def __init__(self, n: int):
# self.seats = list(range(1, n+1))
# heapq.heapify(self.seats)
#
# def reserve(self) -> int:
# return heapq.heappop(self.seats)
#
# def unreserve(self, seatNumber: int) -> None:
# heapq.heappush(self.seats, seatNumber)
# Runtime
# Details
# 368ms
# Beats 98.26%of users with Python3
# Memory
# Details
# 42.48MB
# Beats 95.17%of users with Python3
# https://leetcode.com/problems/seat-reservation-manager/editorial/?envType=daily-question&envId=2023-11-06
# class SeatManager:
#
# def __init__(self, n: int):
# self.seats = []
# self.marker = 1
#
# def reserve(self) -> int:
# if self.seats:
# return heapq.heappop(self.seats)
# result = self.marker
# self.marker += 1
# return result
#
# def unreserve(self, seatNumber: int) -> None:
# heapq.heappush(self.seats, seatNumber)
# Runtime
# Details
# 493ms
# Beats 12.07%of users with Python3
# Memory
# Details
# 42.82MB
# Beats 89.54%of users with Python3
# https://leetcode.com/problems/seat-reservation-manager/editorial/?envType=daily-question&envId=2023-11-06
class SeatManager:
def __init__(self, n: int):
self.seats = SortedSet()
self.marker = 1
def reserve(self) -> int:
if self.seats:
return self.seats.pop(0)
result = self.marker
self.marker += 1
return result
def unreserve(self, seatNumber: int) -> None:
self.seats.add(seatNumber)
# Your SeatManager object will be instantiated and called as such:
# obj = SeatManager(n)
# param_1 = obj.reserve()
# obj.unreserve(seatNumber)
tests = [
[
["SeatManager", "reserve", "reserve", "unreserve", "reserve", "reserve", "reserve", "reserve", "unreserve"],
[[5], [], [], [2], [], [], [], [], [5]],
[null, 1, 2, null, 2, 3, 4, 5, null]
]
]
run_object_tests(tests, cls=SeatManager)