Java, LeetCode | 729. My Calendar I

🚀 풀이 후기

TreeMap에 대해 공부하게 됐습니다.

// 선언 <Key, Value>
TreeMap<Integer, String> treeMap = new TreeMap<>();

// 입력
treeMap.put(key, value);

// 삭제
treeMap.delete(key);
treeMap.clear();

// 조회
treeMap.get(key); // key에 해당하는 value 조회
treeMap.floorKey(key); // key 이하인 값 중 가장 큰 key 조회
treeMap.ceilingKey(key); // key 이상인 값 중 가장 작은 key 조회
treeMap.firstKey(); // 최소 key값
treeMap.lastKey(); // 최대 key값

🌒 문제 설명

달력에 이벤트를 저장합니다. [시작일자, 종료일자) -> (시작일자 포함, 종료일자 미포함)

이벤트 기간은 겹치면 안됩니다.

새로운 이벤트 저장 가능 여부를 반환하면 됩니다. (true / false)

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

A double booking happens when two events have some non-empty intersection 
(i.e., some moment is common to both 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 MyCalendar class:

MyCalendar() 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 double booking. 
Otherwise, return false and do not add the event to the calendar.
 

Example 1:

Input
["MyCalendar", "book", "book", "book"]
[[], [10, 20], [15, 25], [20, 30]]
Output
[null, true, false, true]

Explanation
MyCalendar myCalendar = new MyCalendar();
myCalendar.book(10, 20); // return True
myCalendar.book(15, 25); // return False, It can not be booked because time 15 is already booked by another event.
myCalendar.book(20, 30); // return True, The event can be booked, as the first event takes every time less than 20, but not including 20.
 

Constraints:

0 <= start < end <= 109
At most 1000 calls will be made to book.

🌓 문제 풀이

class MyCalendar {
    List<int[]> events; // 이벤트 기간을 저장하는 리스트. [0]: start, [1]: end

    public MyCalendar() {
        events = new ArrayList<>();
    }

    public boolean book(int start, int end) {
        for (int[] event : events) {
            // 새로 예약할 기간의 시작일자가 기존 종료일자 이상이거나,
            // 새로 예약할 기간의 종료일자가 기존 시작일자 이하이면,
            // 예약할 수 있으므로 continue 합니다.
            if (start >= event[1] || end <= event[0]) {
                continue;
            }
            return false;
        }
        events.add(new int[] { start, end });
        return true;

    }
}

/**
 * Your MyCalendar object will be instantiated and called as such:
 * MyCalendar obj = new MyCalendar();
 * boolean param_1 = obj.book(start,end);
 */

N: book 호출 횟수

- 시간복잡도: O(N^2)

- 공간복잡도: O(N)

🌕 리팩토링

class MyCalendar {
    private TreeMap<Integer, Integer> treeMap;

    public MyCalendar() {
        treeMap = new TreeMap<>();
    }

    public boolean book(int start, int end) {
        Integer prevStart = treeMap.floorKey(start); // 시작일자 이하인 값 중 가장 큰 값
        Integer nextStart = treeMap.ceilingKey(start); // 시작일자 이상인 값 중 가장 작은 값

        if ((prevStart == null || start >= treeMap.get(prevStart)) && (nextStart == null || end <= nextStart)) {
            treeMap.put(start, end);
            return true;
        }
        return false;
    }
}

/**
 * Your MyCalendar object will be instantiated and called as such:
 * MyCalendar obj = new MyCalendar();
 * boolean param_1 = obj.book(start,end);
 */

- 시간복잡도: O(NlogN)

- 공간복잡도: O(N)

 

---

리트코드 문제

깃허브 코드