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

731. My Calendar II

Level

Medium

Description

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 MyCalendar.book, 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(); MyCalendar.book(start, end)

Example 1:

MyCalendar();
MyCalendar.book(10, 20); // returns true
MyCalendar.book(50, 60); // returns true
MyCalendar.book(10, 40); // returns true
MyCalendar.book(5, 15); // returns false
MyCalendar.book(5, 10); // returns true
MyCalendar.book(25, 55); // returns true
Explanation: 
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.

Note:

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

Solution

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 = out.new MyCalendarTwo();

        System.out.println(c.book(24,40));
        System.out.println(c.book(43,50));
        System.out.println(c.book(27,43));
        System.out.println(c.book(5,21));
        System.out.println(c.book(30,40));
        System.out.println(c.book(14,29));
        System.out.println(c.book(3,19));

    }


    //      https://leetcode.com/articles/my-calendar-ii/
    // 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 = obj.book(start,end);
 */
}

############

class MyCalendarTwo {
    private Map<Integer, Integer> tm = new TreeMap<>();

    public MyCalendarTwo() {
    }

    public boolean book(int start, int end) {
        tm.put(start, tm.getOrDefault(start, 0) + 1);
        tm.put(end, tm.getOrDefault(end, 0) - 1);
        int s = 0;
        for (int v : tm.values()) {
            s += v;
            if (s > 2) {
                tm.put(start, tm.get(start) - 1);
                tm.put(end, tm.get(end) + 1);
                return false;
            }
        }
        return true;
    }
}

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

// OJ: https://leetcode.com/problems/my-calendar-ii/
// Time:
//      MyCalendarTwo: O(1)
//      book: O(N)
// Space: O(N)
class MyCalendarTwo {
    map<int, int> m; // number -> diff
public:
    MyCalendarTwo() {}
    bool book(int start, int end) {
        m[start]++;
        m[end]--;
        int sum = 0;
        for (auto &[n, d] : m) {
            sum += d;
            if (sum > 2) {
                if (--m[start] == 0) m.erase(start);
                if (++m[end] == 0) m.erase(end);
                return false;
            }
        }
        return true;
    }
};

from sortedcontainers import SortedDict

class MyCalendarTwo:
    def __init__(self):
        self.sd = SortedDict() # cannot be dict like self.sd={}

    def book(self, start: int, end: int) -> bool:
        self.sd[start] = self.sd.get(start, 0) + 1
        self.sd[end] = self.sd.get(end, 0) - 1
        s = 0
        for v in self.sd.values():
            s += v
            if s > 2:
                self.sd[start] -= 1
                self.sd[end] += 1
                return False
        return True


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

############

class MyCalendarTwo(object):

    def __init__(self):
        # 每个被book了的区间
        self.booked = list()
        # 每个重叠了的区间
        self.overlaped = list()

    def book(self, start, end):
        """
        :type start: int
        :type end: int
        :rtype: bool
        """
        for os, oe in self.overlaped:
            if max(os, start) < min(oe, end):
                return False
        for bs, be in self.booked:
            ss = max(bs, start)
            ee = min(be, end)
            if ss < ee:
                self.overlaped.append((ss, ee))
        self.booked.append((start, end))
        return True


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

type MyCalendarTwo struct {
	*redblacktree.Tree
}

func Constructor() MyCalendarTwo {
	return MyCalendarTwo{redblacktree.NewWithIntComparator()}
}

func (this *MyCalendarTwo) Book(start int, end int) bool {
	add := func(key, val int) {
		if v, ok := this.Get(key); ok {
			this.Put(key, v.(int)+val)
		} else {
			this.Put(key, val)
		}
	}
	add(start, 1)
	add(end, -1)
	s := 0
	it := this.Iterator()
	for it.Next() {
		s += it.Value().(int)
		if s > 2 {
			add(start, -1)
			add(end, 1)
			return false
		}
	}
	return true
}

/**
 * Your MyCalendarTwo object will be instantiated and called as such:
 * obj := Constructor();
 * param_1 := obj.Book(start,end);
 */

731 - My Calendar II

731. My Calendar II

Level

Description

Solution

All Problems

All Solutions

Welcome to Subscribe On Youtube

731. My Calendar II

Level

Description

Solution

All Problems

All Solutions