[LeetCode] 731. My Calendar II

https://leetcode.com/problems/my-calendar-ii/description/?envType=daily-question&envId=2024-09-27

leetcode - My Calendar II

문제 유형 : 구현, 라인 스위핑

문제 난이도 : Medium

 

문제

You are implementing a program to use as your calendar. We can add a new event if adding the event will not cause a triple booking.

A triple booking happens when three events have some non-empty intersection (i.e., some moment is common to all the three events.).

The event can be represented as a pair of integers start and end that represents a booking on the half-open interval [start, end), the range of real numbers x such that start <= x < end.

Implement the MyCalendarTwo class:

• MyCalendarTwo() Initializes the calendar object.
• boolean book(int start, int end) Returns true if the event can be added to the calendar successfully without causing a triple booking. Otherwise, return false and do not add the event to the calendar.

 

캘린더 프로그램을 구현해야 한다.

삼중 예약을 하면 안된다.

삼중 예약은 동시간에 3개 이상의 스케줄이 잡히는 것을 의미한다.

이벤트는 두 정수의 쌍 start, end로 주어진다. start일부터 시작해서 end일 전까지 한다.

MyCalendar 클래스를 구현하시오.

 

- MyCalendarTwo()는 캘린더 객체를 초기화한다.

- boolean book(int start, int end)는 일정추가에 성공하면 true, 삼중 부킹으로 인한 실패 시 false를 반환해야 한다.

 

풀이

map에 스케줄 수의 변화를 저장할 것이다.

timeline[start]에는 1을 추가하고,

timeline[end]에는 1을 뺀다.

 

그리고, 현재 스케줄수인 ongoing변수를 만들어 0으로 초기화하고,

map을 순차적으로 읽으면서 변화량을 누적하여 현재 스케줄수를 업데이트하고, 만약 3이 넘으면, timeline에 준 변화를 되돌리고 false를 반환한다.

무사히 순회했다면, true를 반환하면 된다.

 

코드

C++

class MyCalendarTwo {
    map<int, int> timeline;
public:
    MyCalendarTwo() {}
    
    bool book(int start, int end) {
        timeline[start] += 1;
        timeline[end] -= 1;
        
        int ongoing = 0;
        for(auto &[time, delta] : timeline){
            ongoing += delta;
            if(ongoing >= 3){
                timeline[start] -= 1;
                timeline[end] += 1;
                return false;
            }
        }
        return true;
    }
};