Created
April 11, 2024 03:21
-
-
Save hungngocphat01/fddb732b0e30715f2b2b9dc238391511 to your computer and use it in GitHub Desktop.
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| from typing import Optional | |
| from dataclasses import dataclass, field | |
| @dataclass | |
| class Reservation: | |
| start: int | |
| end: int | |
| def overlap(self, other: "Reservation") -> bool: | |
| return not ( | |
| ((other.start < self.start) & (other.end < self.start)) | |
| | (other.start > self.end) | |
| ) | |
| # Unit test | |
| base_res = Reservation(30, 50) | |
| assert base_res.overlap(Reservation(20, 35)) == True | |
| assert base_res.overlap(Reservation(20, 25)) == False | |
| assert base_res.overlap(Reservation(35, 40)) == True | |
| assert base_res.overlap(Reservation(55, 60)) == False | |
| assert base_res.overlap(Reservation(20, 60)) == True | |
| @dataclass | |
| class TreeNode: | |
| value: Reservation | |
| left: Optional["TreeNode"] = field(default=None) | |
| right: Optional["TreeNode"] = field(default=None) | |
| class SearchTree: | |
| def __init__(self): | |
| self.root = None | |
| def insert(self, res: Reservation, root: TreeNode = None): | |
| # null root | |
| if self.root is None: | |
| self.root = TreeNode(res) | |
| return | |
| root = root or self.root | |
| # check overlap with current node | |
| if root.value.overlap(res): | |
| raise ValueError("Found overlapped reservation: " + str(root)) | |
| # insert left-right | |
| if res.start < root.value.start: | |
| if root.left is None: | |
| root.left = TreeNode(res) | |
| return | |
| self.insert(res, root.left) | |
| else: | |
| if root.right is None: | |
| root.right = TreeNode(res) | |
| return | |
| self.insert(res, root.right) | |
| def main(): | |
| tree = SearchTree() | |
| # should insert | |
| tree.insert(Reservation(30, 50)) | |
| tree.insert(Reservation(20, 25)) | |
| tree.insert(Reservation(55, 60)) | |
| tree.insert(Reservation(65, 70)) | |
| # should raise | |
| try: | |
| tree.insert(Reservation(10, 80)) | |
| tree.insert(Reservation(67, 68)) | |
| except: ... | |
| else: | |
| raise AssertionError("Why not raised?") |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment