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
6def closest_left_neighbor(items: list[int], value: int, *, count: int) -> int:
7 """Find the closest left neighbor to start in ends."""
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
19 return min(r_start, r_stop)
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.
35 If so, say where. If not, say where.
36 """
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
52 return True, pos
55class MyCalendarTwo:
56 starts_p: list[int]
57 starts_q: list[int]
58 ends_p: list[int]
59 ends_q: list[int]
61 def __init__(self):
62 self.count_p = 0
63 self.count_q = 0
65 self.starts_p = list()
66 self.starts_q = list()
68 self.ends_p = list()
69 self.ends_q = list()
71 def book(self, start: int, end: int) -> bool:
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
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
99 # NOTE: If not $P$ schedulable, find intersecting.
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 )
109 start_intersects_before = self.starts_p[index_intersects_before]
110 end_intersects_after = self.ends_p[index_intersects_after]
112 contains_start = min(start_intersects_before, start)
113 contains_end = max(end_intersects_after, end)
115 if index_intersects_before == index_intersects_after:
116 index_intersects_after += 1
118 contained_start = self.starts_p[index_intersects_before:index_intersects_after]
119 contained_end = self.ends_p[index_intersects_before:index_intersects_after]
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 )
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 ]
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 ]
158 return True
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
224@pytest.fixture
225def solution():
226 return MyCalendarTwo()
229with open(pathlib.Path(__file__).resolve().parent / "cases.yaml") as file:
230 cases = list(item.values() for item in yaml.safe_load(file))
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):
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)))
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"
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 )
259 assert aa_computed == aa, f"Expected `{aa}`, got `{aa_computed}`."
262# Your MyCalendarTwo object will be instantiated and called as such:
263# obj = MyCalendarTwo()
264# param_1 = obj.book(star