Formatted question description:

731. My Calendar II




Implement a MyCalendarTwo class to store your events. A new event can be added if adding the event will not cause a triple booking.

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 triple booking happens when three events have some non-empty intersection (ie., there is some time that is common to all 3 events.)

For each call to the method, return 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.

Your class will be called like this: MyCalendar cal = new MyCalendar();, end)

Example 1:

MyCalendar();, 20); // returns true, 60); // returns true, 40); // returns true, 15); // returns false, 10); // returns true, 55); // returns true
The first two events can be booked.  The third event can be double booked.
The fourth event (5, 15) can't be booked, because it would result in a triple booking.
The fifth event (5, 10) can be booked, as it does not use time 10 which is already double booked.
The sixth event (25, 55) can be booked, as the time in [25, 40) will be double booked with the third event;
the time [40, 50) will be single booked, and the time [50, 55) will be double booked with the second event.


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


Use two lists to store the intervals of booking and the overlapping intervals, which are both sorted. Each time book(int start, int end) is called, loop over the list of overlaps to see whether there will be a new overlap.

  • If so, then adding the new interval will cause a triple booking, so return false.
  • Otherwise, add the new interval and the new overlapping intervals into the two list respectively, sort the two lists, and return true.
public class My_Calendar_II {

    public static void main (String[] args) {
        My_Calendar_II out = new My_Calendar_II();
        MyCalendarTwo c = MyCalendarTwo();



    // start End Map
    class MyCalendarTwo {
        // time => its counts
        TreeMap<Integer, Integer> timeCountMap; // @note: HashMap不行,因为map.value()没有排序

        public MyCalendarTwo() {
            timeCountMap = new TreeMap<>();

        public boolean book(int start, int end) {
            // 在for遍历的时候,如果一段时间,那么先是start的1,然后end的-1,那么active += d就会是0
            timeCountMap.put(start, timeCountMap.getOrDefault(start, 0) + 1);
            timeCountMap.put(end, timeCountMap.getOrDefault(end, 0) - 1);

            int active = 0;
            for (int d: timeCountMap.values()) { // ordered? yes, because it's TreeMap!
                active += d;
                if (active >= 3) { // undo this start/end update
                    timeCountMap.put(start, timeCountMap.get(start) - 1);
                    timeCountMap.put(end, timeCountMap.get(end) + 1);

                    // remove below 2 if, will also work
                    if (timeCountMap.get(start) == 0) {
                        timeCountMap.remove(start); // remove key
                    if (timeCountMap.get(end) == 0) {
                        timeCountMap.remove(end); // remove key

                    return false;

            return true;

    public class MyCalendarTwo_BruteForce {
        List<int[]> calendar;
        List<int[]> overlaps;

        MyCalendarTwo_BruteForce() {
            calendar = new ArrayList<>();
            overlaps = new ArrayList<>();

        public boolean book(int start, int end) {
            for (int[] interval: overlaps) {
                if (interval[0] < end && start < interval[1]) {
                    return false;

            // update overlaps if any
            for (int[] interval: calendar) {
                if (interval[0] < end && start < interval[1]) {
                    overlaps.add(new int[]{
                                            Math.max(start, interval[0]),
                                            Math.min(end, interval[1])
            calendar.add(new int[]{start, end});

            return true;
 * Your MyCalendarTwo object will be instantiated and called as such:
 * MyCalendarTwo obj = new MyCalendarTwo();
 * boolean param_1 =,end);

All Problems

All Solutions