Coverage for blog/dsa/leetcode/chair_numbers/__init__.py: 35%

1import pytest 

2import heapq 

3 

4 

5class SolutionTLE: 

6 

7 def smallestChair(self, times: list[list[int]], targetFriend: int) -> int: 

8 

9 occupied: dict[int, int] = {} 

10 last_time = -1 

11 

12 final = 0 

13 opened = set() 

14 

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) 

23 

24 if opened: 

25 seat_number = min(opened) 

26 opened.remove(seat_number) 

27 else: 

28 seat_number = final 

29 final += 1 

30 

31 if pos == targetFriend: 

32 return seat_number 

33 

34 occupied[seat_number] = vacates 

35 last_time = time 

36 

37 return -1 

38 

39 

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 

45 

46 final = 0 

47 

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) 

55 

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 

61 

62 seat_number = _seat_number 

63 else: 

64 seat_number = final 

65 final += 1 

66 

67 if pos == targetFriend: 

68 return seat_number 

69 

70 occupied[seat_number] = vacates 

71 last_time = time 

72 

73 return -1 

74 # end snippet solution 

75 

76 

77# start snippet solution_min_heap 

78class SolutionMinHeap: 

79 

80 def smallestChair(self, times: list[list[int]], targetFriend: int) -> int: 

81 occupied: dict[int, int] = {} 

82 available: list[int] = [] 

83 last_time = -1 

84 

85 final = 0 

86 

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) 

94 

95 if available: 

96 seat_number = heapq.heappop(available) 

97 else: 

98 seat_number = final 

99 final += 1 

100 

101 if pos == targetFriend: 

102 return seat_number 

103 

104 occupied[seat_number] = vacates 

105 last_time = time 

106 

107 return -1 

108 # end snippet solution_min_heap 

109 

110 

111# start snippet solution_editorial 

112class Solution: 

113 

114 def smallestChair(self, times: list[list[int]], targetFriend: int) -> int: 

115 

116 events = [] 

117 for index, (time_start, time_stop) in enumerate(times): 

118 events.append([time_start, index]) 

119 events.append([time_stop, ~index]) 

120 

121 events.sort(key=lambda pair: pair[0]) 

122 

123 vacant = list(range(len(times))) 

124 occupied: list[tuple[int, int]] = list() 

125 

126 for time, pos in events: 

127 

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) 

132 

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)) 

137 

138 if pos == targetFriend: 

139 return vacant_index 

140 

141 return -1 

142 # end snippet solution_editorial 

143 

144 

145@pytest.fixture 

146def solution(): 

147 return Solution() 

148 

149 

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): 

167 

168 answer_computed = solution.smallestChair(times, target_friend) # type: ignore 

169 assert answer == answer_computed