[BST 이진검색트리] 729. My Calendar I ★★★

729. My Calendar I

 

https://youtu.be/fIxck3tlId4

 

class MyCalendar:
    def __init__(self):
        # 예약된 일정들을 저장할 리스트 (각 요소는 (start, end) 튜플)
        self.events = []

    def book(self, startTime: int, endTime: int) -> bool:
        # 기존에 예약된 모든 일정과 하나씩 비교하면서 겹치는지 확인
        for start, end in self.events:
            # 겹치는 조건: 두 구간이 공통 범위를 가질 때
            # 즉, [startTime, endTime)와 [start, end)가 겹치면 False 반환
            if startTime < end and start < endTime:
                return False  # 겹치는 예약이 있으므로 추가 불가

        # 겹치는 예약이 없으면, 새 일정을 추가하고 True 반환
        self.events.append((startTime, endTime))
        return True

 

이진 탐색 트리 (BST) 구조로 푸는 방식

# 예약 정보를 노드로 표현하는 이진 탐색 트리
class Tree:
    def __init__(self, start: int, end: int):
        self.left = None      # 왼쪽 자식 노드 (start 시간 기준으로 더 이른 예약)
        self.right = None     # 오른쪽 자식 노드 (더 늦은 예약)
        self.start = start    # 현재 예약 시작 시간
        self.end = end        # 현재 예약 종료 시간

    # 새 예약 구간 [start, end) 을 삽입
    def insert(self, start, end):
        curr = self  # 루트부터 시작
        while True:
            # 새 예약이 현재 예약보다 늦게 시작되고, 겹치지 않음
            if start >= curr.end:
                if not curr.right:
                    # 오른쪽에 새 노드를 삽입
                    curr.right = Tree(start, end)
                    return True
                # 오른쪽 서브트리로 이동
                curr = curr.right
            # 새 예약이 현재 예약보다 일찍 끝나고, 겹치지 않음
            elif end <= curr.start:
                if not curr.left:
                    # 왼쪽에 새 노드를 삽입
                    curr.left = Tree(start, end)
                    return True
                # 왼쪽 서브트리로 이동
                curr = curr.left
            else:
                # 겹치는 경우 → False 반환
                return False

# MyCalendar 클래스 정의
class MyCalendar:

    def __init__(self):
        self.root = None  # 예약 트리의 루트 노드

    def book(self, startTime: int, endTime: int) -> bool:
        # 첫 예약이면 루트 노드로 삽입
        if not self.root:
            self.root = Tree(startTime, endTime)
            return True
        # 루트 노드로부터 삽입 시작
        return self.root.insert(startTime, endTime)



# Your MyCalendar object will be instantiated and called as such:
# obj = MyCalendar()
# param_1 = obj.book(startTime,endTime)

 

BST (bisect) 사용

import bisect

class MyCalendar:

    def __init__(self):
        self.starts = []  # 예약 시작 시간 리스트 (정렬됨)
        self.ends = []    # 예약 종료 시간 리스트 (같은 인덱스로 매칭됨)

    def book(self, startTime: int, endTime: int) -> bool:
        # 예약 시작 시간을 기준으로 삽입할 위치 찾기
        i = bisect.bisect_right(self.starts, startTime)

        # 왼쪽 예약과 겹치는지 확인
        if i > 0 and self.ends[i - 1] > startTime:
            return False

        # 오른쪽 예약과 겹치는지 확인
        if i < len(self.starts) and self.starts[i] < endTime:
            return False

        # 겹치지 않으면 삽입
        self.starts.insert(i, startTime)
        self.ends.insert(i, endTime)
        return True