732. My Calendar III

문제

A k-booking happens when k events have some non-empty intersection (i.e., there is some time that is common to all k events.)

You are given some events [start, end), after each given event, return an integer k representing the maximum k-booking between all the previous events.

Implement the MyCalendarThree class:

-MyCalendarThree() Initializes the object.

-int book(int start, int end) Returns an integer k representing the largest integer such that there exists a k-booking in the calendar.

https://leetcode.com/problems/my-calendar-iii/

접근

#디자인 #정렬 set #이분탐색

단순히 완전탐색으로 진행하면 시간초과가 나므로, 시작점/끝점과 중복이벤트의 수만을 담은 SortedList를 사용한다.

start,end값을 받아오면, 각 점에 해당하는 리스트를 추가한다. 이 때, 기존에 같은 시간대가 존재한다면 추가하지 않고 리턴한다. 추가할 때의 초기 이벤트의 수는 바로 직전 원소의 이벤트의 수와 같다.(이벤트가 지속되고 있으므로)

모든 리스트가 세팅되었으면, 받아온 [start:end) 범위만큼 순회하며 해당하는 원소의 이벤트 수를 1씩 증가시킨다. 이 때 답이 될 res값과 비교하며, 최대값이 갱신되면 res도 갱신된다.

코드

from sortedcontainers import SortedList

class MyCalendarThree:

    def __init__(self):
        self.starts = SortedList([[0,0]]) # [시작점, 중복 이벤트의 수]
        self.res = 0

    def split(self, x: int) -> None:
        idx = self.starts.bisect_left([x,0]) # self.starts에서 [x,0]의 위치를 찾는 이분탐색(왼쪽우선)
        
        if idx < len(self.starts) and self.starts[idx][0] == x: # 만약 그 결과가 배열의 길이보다 작고 제대로 들어가 있으면
            return idx # 리턴
        
        self.starts.add([x,self.starts[idx-1][1]]) # 아닐 시, starts에 [ x, 직전 값의 중복 이벤트 수 ]추가

    def book(self, start: int, end: int) -> int:
        self.split(start)
        self.split(end) # 각 점을 인자로 해 split
        
        for interval in self.starts.irange([start,0], [end,0], (True,False)):
            interval[1] += 1 # start와 end 사이의 모든 값에 대해 중복 이벤트 수 추가
            self.res = max(self.res, interval[1]) # 현재 최대값과 interval의 값 비교

        return self.res
        


# Your MyCalendarThree object will be instantiated and called as such:
# obj = MyCalendarThree()
# param_1 = obj.book(start,end)

효율성

Runtime: 656 ms, faster than 86.46% of Python3 online submissions for My Calendar III.
Memory Usage: 14.9 MB, less than 24.31% of Python3 online submissions for My Calendar III.