Coverage for blog/dsa/leetcode/chair_numbers/__init__.py: 35%
93 statements
« prev ^ index » next coverage.py v7.6.12, created at 2025-02-20 16:23 +0000
« prev ^ index » next coverage.py v7.6.12, created at 2025-02-20 16:23 +0000
1import pytest
2import heapq
5class SolutionTLE:
7 def smallestChair(self, times: list[list[int]], targetFriend: int) -> int:
9 occupied: dict[int, int] = {}
10 last_time = -1
12 final = 0
13 opened = set()
15 for pos, (time, vacates) in sorted(
16 enumerate(times), key=lambda items: items[1][0]
17 ):
18 if time != last_time:
19 for k in range(final):
20 if k in occupied and occupied[k] <= time:
21 occupied.pop(k)
22 opened.add(k)
24 if opened:
25 seat_number = min(opened)
26 opened.remove(seat_number)
27 else:
28 seat_number = final
29 final += 1
31 if pos == targetFriend:
32 return seat_number
34 occupied[seat_number] = vacates
35 last_time = time
37 return -1
40# start snippet solution
41class SolutionWorks:
42 def smallestChair(self, times: list[list[int]], targetFriend: int) -> int:
43 occupied: dict[int, int] = {}
44 last_time = -1
46 final = 0
48 for pos, (time, vacates) in sorted(
49 enumerate(times), key=lambda items: items[1][0]
50 ):
51 if time != last_time:
52 for k in list(occupied.keys()):
53 if occupied[k] <= time:
54 occupied.pop(k)
56 if len(occupied) != final:
57 _seat_number = final
58 for _seat_number in range(final):
59 if _seat_number not in occupied:
60 break
62 seat_number = _seat_number
63 else:
64 seat_number = final
65 final += 1
67 if pos == targetFriend:
68 return seat_number
70 occupied[seat_number] = vacates
71 last_time = time
73 return -1
74 # end snippet solution
77# start snippet solution_min_heap
78class SolutionMinHeap:
80 def smallestChair(self, times: list[list[int]], targetFriend: int) -> int:
81 occupied: dict[int, int] = {}
82 available: list[int] = []
83 last_time = -1
85 final = 0
87 for pos, (time, vacates) in sorted(
88 enumerate(times), key=lambda items: items[1][0]
89 ):
90 if time != last_time:
91 for k in list(k for k, v in occupied.items() if v <= time):
92 occupied.pop(k)
93 heapq.heappush(available, k)
95 if available:
96 seat_number = heapq.heappop(available)
97 else:
98 seat_number = final
99 final += 1
101 if pos == targetFriend:
102 return seat_number
104 occupied[seat_number] = vacates
105 last_time = time
107 return -1
108 # end snippet solution_min_heap
111# start snippet solution_editorial
112class Solution:
114 def smallestChair(self, times: list[list[int]], targetFriend: int) -> int:
116 events = []
117 for index, (time_start, time_stop) in enumerate(times):
118 events.append([time_start, index])
119 events.append([time_stop, ~index])
121 events.sort(key=lambda pair: pair[0])
123 vacant = list(range(len(times)))
124 occupied: list[tuple[int, int]] = list()
126 for time, pos in events:
128 # Mark all chairs as vacated for the friends which have left.
129 while occupied and occupied[0][0] <= time:
130 _, vacated_index = heapq.heappop(occupied)
131 heapq.heappush(vacant, vacated_index)
133 # Mark chair occupied if the friend is ariving.
134 if pos > -1:
135 vacant_index = heapq.heappop(vacant)
136 heapq.heappush(occupied, (times[pos][1], vacant_index))
138 if pos == targetFriend:
139 return vacant_index
141 return -1
142 # end snippet solution_editorial
145@pytest.fixture
146def solution():
147 return Solution()
150@pytest.mark.parametrize(
151 "times, target_friend, answer",
152 (
153 ([(1, 4), (2, 3), (4, 6)], 1, 1),
154 ([(3, 10), (1, 2), (1, 3), (1, 5), (2, 6)], 0, 1),
155 ([[3, 10], [1, 5], [2, 6]], 0, 2),
156 ([[1, 2], [2, 3]], 1, 0),
157 ([[4, 5], [6, 8], [8, 10], [1, 8]], 2, 0),
158 ([[7, 10], [6, 7], [1, 3], [2, 7], [4, 5]], 0, 0),
159 ([[99999, 100000], [1, 2]], 1, 0),
160 ([[2, 4], [4, 9], [3, 4], [6, 8], [5, 10]], 4, 1),
161 ([(k, 10000) for k in range(10000)], 9998, 9998),
162 ),
163)
164def test_solution(
165 solution: Solution, times: list[tuple[int, int]], target_friend: int, answer: int
166):
168 answer_computed = solution.smallestChair(times, target_friend) # type: ignore
169 assert answer == answer_computed