Coverage for blog/dsa/leetcode/calendar_2/__init__.py: 22%

86 statements  

« prev     ^ index     » next       coverage.py v7.6.12, created at 2025-02-20 16:23 +0000

1import pytest 

2import yaml 

3from kagglehub.gcs_upload import pathlib 

4 

5 

6def closest_left_neighbor(items: list[int], value: int, *, count: int) -> int: 

7 """Find the closest left neighbor to start in ends.""" 

8 

9 r_start, r_stop = 0, count 

10 r_middle = -1 

11 while r_start < r_stop - 1: 

12 r_middle = (r_start + r_stop) // 2 

13 middle = items[r_middle] 

14 if value < middle: 

15 r_stop = r_middle 

16 else: 

17 r_start = r_middle 

18 

19 return min(r_start, r_stop) 

20 

21 

22def is_schedulable( 

23 starts: list[int], 

24 ends: list[int], 

25 *, 

26 count: int, 

27 start: int, 

28 end: int, 

29) -> tuple[ 

30 bool, 

31 int, 

32]: 

33 """Determine if the event is schedulable in the provided schedule. 

34 

35 If so, say where. If not, say where. 

36 """ 

37 

38 if count == 0: 

39 pos = 0 

40 elif ends[-1] <= start: 

41 pos = count 

42 elif starts[0] >= end: 

43 pos = 0 

44 else: 

45 after_index = closest_left_neighbor(ends, start, count=count) 

46 pos = after_index + 1 

47 if start < ends[after_index]: 

48 return False, after_index 

49 elif pos < count and end > starts[pos]: 

50 return False, pos 

51 

52 return True, pos 

53 

54 

55class MyCalendarTwo: 

56 starts_p: list[int] 

57 starts_q: list[int] 

58 ends_p: list[int] 

59 ends_q: list[int] 

60 

61 def __init__(self): 

62 self.count_p = 0 

63 self.count_q = 0 

64 

65 self.starts_p = list() 

66 self.starts_q = list() 

67 

68 self.ends_p = list() 

69 self.ends_q = list() 

70 

71 def book(self, start: int, end: int) -> bool: 

72 

73 # NOTE: Check $Q$ schedulable. 

74 is_schedulable_q, left_index_q = is_schedulable( 

75 self.starts_q, 

76 self.ends_q, 

77 count=self.count_q, 

78 start=start, 

79 end=end, 

80 ) 

81 if not is_schedulable_q: 

82 return False 

83 

84 # NOTE: Check $P$ schedulable. 

85 is_schedulable_p, p_left_index = is_schedulable( 

86 self.starts_p, 

87 self.ends_p, 

88 count=self.count_p, 

89 start=start, 

90 end=end, 

91 ) 

92 if is_schedulable_p: 

93 print(p_left_index) 

94 self.count_p += 1 

95 self.starts_p.insert(p_left_index, start) 

96 self.ends_p.insert(p_left_index, end) 

97 return True 

98 

99 # NOTE: If not $P$ schedulable, find intersecting. 

100 

101 # nearest end before start, closest start after end 

102 index_intersects_before = closest_left_neighbor( 

103 self.ends_p, start, count=self.count_p 

104 ) 

105 index_intersects_after = closest_left_neighbor( 

106 self.starts_p, end, count=self.count_p 

107 ) 

108 

109 start_intersects_before = self.starts_p[index_intersects_before] 

110 end_intersects_after = self.ends_p[index_intersects_after] 

111 

112 contains_start = min(start_intersects_before, start) 

113 contains_end = max(end_intersects_after, end) 

114 

115 if index_intersects_before == index_intersects_after: 

116 index_intersects_after += 1 

117 

118 contained_start = self.starts_p[index_intersects_before:index_intersects_after] 

119 contained_end = self.ends_p[index_intersects_before:index_intersects_after] 

120 

121 print( 

122 { 

123 "start": start, 

124 "end": end, 

125 "index_intersects_before": index_intersects_before, 

126 "index_intersects_after": index_intersects_after, 

127 "start_intersects_before": start_intersects_before, 

128 "end_intersects_after": end_intersects_after, 

129 "contains_start": contains_start, 

130 "contains_end": contains_end, 

131 "contained_start": contained_start, 

132 "contained_end": contained_end, 

133 } 

134 ) 

135 

136 self.starts_p = [ 

137 *self.starts_p[:index_intersects_before], 

138 contains_start, 

139 *self.starts_p[index_intersects_after:], 

140 ] 

141 self.ends_p = [ 

142 *self.ends_p[:index_intersects_before], 

143 contains_end, 

144 *self.ends_p[index_intersects_after:], 

145 ] 

146 

147 self.starts_q = [ 

148 *self.starts_q[: left_index_q + 1], 

149 *contained_start, 

150 *self.starts_q[left_index_q:], 

151 ] 

152 self.ends_q = [ 

153 *self.ends_q[: left_index_q + 1], 

154 *contained_end, 

155 *self.ends_q[left_index_q:], 

156 ] 

157 

158 return True 

159 

160 # def book(self, start: int, end: int) -> bool: 

161 # 

162 # # NOTE: Try to book in $P$ and $Q$. 

163 # p_booked, p_after = book( 

164 # self.starts_p, self.ends_p, count=self.count_p, start=start, end=end 

165 # ) 

166 # if p_booked: 

167 # print(f"Booked `{(start, end)}` in `p`.") 

168 # self.count_p += 1 

169 # return True 

170 # 

171 # q_booked, q_after = book( 

172 # self.starts_q, self.ends_q, count=self.count_q, start=start, end=end 

173 # ) 

174 # if q_booked: 

175 # print(f"Booked `{(start, end)}` in `q`.") 

176 # self.count_q += 1 

177 # return True 

178 # 

179 # # NOTE: See if collisions in $P$ and $Q$ intersect, if not, split 

180 # # and book chunks. 

181 # pp = (self.starts_p[p_after], self.ends_p[p_after]) 

182 # qq = (self.starts_q[q_after], self.ends_q[q_after]) 

183 # 

184 # if pp[0] < qq[0]: 

185 # left, right = pp, qq 

186 # p_start, p_end = right[0], end 

187 # q_start, q_end = start, right[0] 

188 # else: 

189 # left, right = qq, pp 

190 # p_start, p_end = start, right[0] 

191 # q_start, q_end = right[0], end 

192 # 

193 # print(f"`{p_after = }`", f"`{q_after = }`") 

194 # print(f"`{left = }`, `{right = }`.") 

195 # 

196 # # If the end of the left event exceeds the right event, unschedulable. 

197 # if left[1] > right[0]: 

198 # print(f"Could not book `{(start, end)}`.") 

199 # return False 

200 # 

201 # print(f"Split `{(start, end)}` at `{right[0]}`.") 

202 # p_booked, p_after = book( 

203 # self.starts_p, self.ends_p, count=self.count_p, start=p_start, end=p_end 

204 # ) 

205 # if not p_booked: 

206 # print(f"Failed to book `{(start, right[0])}` in p") 

207 # return False 

208 # 

209 # q_booked, _ = book( 

210 # self.starts_q, self.ends_q, count=self.count_q, start=q_start, end=q_end 

211 # ) 

212 # if not q_booked: 

213 # print(f"Failed to book `{(right[0], end)}` in q") 

214 # self.starts_p.pop(p_after) 

215 # self.ends_p.pop(p_after) 

216 # return False 

217 # 

218 # self.count_p += 1 

219 # self.count_q += 1 

220 # 

221 # return True 

222 

223 

224@pytest.fixture 

225def solution(): 

226 return MyCalendarTwo() 

227 

228 

229with open(pathlib.Path(__file__).resolve().parent / "cases.yaml") as file: 

230 cases = list(item.values() for item in yaml.safe_load(file)) 

231 

232 

233@pytest.mark.skip 

234@pytest.mark.parametrize("question, answer", cases) 

235def test_solution( 

236 solution: MyCalendarTwo, 

237 question: list[tuple[int, int]], 

238 answer: list[bool], 

239): 

240 

241 for (start, end), aa in zip(question, answer): 

242 print("===========================================") 

243 aa_computed = solution.book(start, end) 

244 print(list(zip(solution.starts_p, solution.ends_p))) 

245 print(list(zip(solution.starts_q, solution.ends_q))) 

246 

247 assert solution.starts_p == sorted(solution.starts_p), "``starts_p`` not sorted" 

248 assert solution.ends_p == sorted(solution.ends_p), "``ends_p`` not sorted" 

249 assert solution.starts_q == sorted(solution.starts_q), "``starts_q`` not sorted" 

250 assert solution.ends_q == sorted(solution.ends_q), "``ends_p`` not sorted" 

251 

252 assert all( 

253 solution.starts_p[k] <= solution.ends_p[k] for k in range(solution.count_p) 

254 ) 

255 assert all( 

256 solution.starts_q[k] <= solution.ends_q[k] for k in range(solution.count_q) 

257 ) 

258 

259 assert aa_computed == aa, f"Expected `{aa}`, got `{aa_computed}`." 

260 

261 

262# Your MyCalendarTwo object will be instantiated and called as such: 

263# obj = MyCalendarTwo() 

264# param_1 = obj.book(star