Formatted question description: https://leetcode.ca/all/732.html

732. My Calendar III

Level

Hard

Description

Implement a MyCalendarThree class to store your events. A new event can always be added.

Your class will have one method, book(int start, int end). Formally, this represents a booking on the half open interval [start, end), the range of real numbers x such that start <= x < end.

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

For each call to the method MyCalendar.book, return an integer K representing the largest integer such that there exists a K-booking in the calendar.

Your class will be called like this: MyCalendarThree cal = new MyCalendarThree(); MyCalendarThree.book(start, end)

Example 1:

MyCalendarThree();
MyCalendarThree.book(10, 20); // returns 1
MyCalendarThree.book(50, 60); // returns 1
MyCalendarThree.book(10, 40); // returns 2
MyCalendarThree.book(5, 15); // returns 3
MyCalendarThree.book(5, 10); // returns 3
MyCalendarThree.book(25, 55); // returns 3
Explanation: 
The first two events can be booked and are disjoint, so the maximum K-booking is a 1-booking.
The third event [10, 40) intersects the first event, and the maximum K-booking is a 2-booking.
The remaining events cause the maximum K-booking to be only a 3-booking.
Note that the last event locally causes a 2-booking, but the answer is still 3 because
eg. [10, 20), [10, 40), and [5, 15) are still triple booked.

Note:

• The number of calls to MyCalendarThree.book per test case will be at most 400.
• In calls to MyCalendarThree.book(start, end), start and end are integers in the range [0, 10^9].

Solution

Use TreeMap, which contains all keys in sorted order. Each time book(int start, int end) is called, update the values of the keys start and end in the map by increasing the value of key start by 1 and decreasing the value of key end by 1. Then loop over all the keys in the map to obtain the booking count of each time and the maximum booking, and return the maximum booking.

import java.util.TreeMap;

public class My_Calendar_III {

    // ref: https://leetcode.com/articles/my-calendar-iii/

    // `start+1` and `end-1`
    class MyCalendarThree {

        TreeMap<Integer, Integer> timeCountMap;

        public MyCalendarThree() {
            timeCountMap = new TreeMap<>();
        }

        public int book(int start, int end) {

            timeCountMap.put(start, timeCountMap.getOrDefault(start, 0) + 1);
            timeCountMap.put(end, timeCountMap.getOrDefault(end, 0) - 1);

            int active = 0;
            int result = 0;

            for (int d : timeCountMap.values()) {
                active += d;
                result = Math.max(result, active);
            }

            return result;
        }
    }
}

All Problems

All Solutions