LeetCode 729 - My Calendar I

Related: LeetCode 729 - My Calendar I
LeetCode 731 - My Calendar II
LeetCode 732 - My Calendar III
https://leetcode.com/problems/my-calendar-i/solution/

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

Your class will have the 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 double booking happens when two events have some non-empty intersection (ie., there is some time that is common to both events.)

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

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(15, 25); // returns false
MyCalendar.book(20, 30); // returns true
Explanation: 
The first event can be booked.  The second can't because time 15 is already booked by another event.
The third event can be booked, as the first event takes every time less than 20, but not including 20.

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].

X. Using TreeMap

• Time Complexity (Java): $O(N \log N)$, where $N$ is the number of events booked. For each new event, we search that the event is legal in $O(\log N)$ time, then insert it in $O(1)$ time.
• Time Complexity (Python): $O(N^2)$ worst case, with $O(N \log N)$ on random data. For each new event, we insert the event into our binary tree. As this tree may not be balanced, it may take a linear number of steps to add each event.
• Space Complexity: $O(N)$, the size of the data structures used.

X. https://leetcode.com/problems/my-calendar-i/discuss/109473/JAVA-Simple-6-line-Solution-TreeMap-lowerEntry

    TreeMap tm;

    public MyCalendar() {
        tm = new TreeMap<Integer, Integer>();
    }
    
    public boolean book(int start, int end) {
        Map.Entry<Integer, Integer> entry = tm.lowerEntry(end);
        if (entry != null && entry.getValue() > start) return false;
        tm.put(start, end);
        return true;
    }

https://leetcode.com/problems/my-calendar-i/discuss/109462/Java-8-liner-TreeMap

    TreeMap<Integer, Integer> calendar;

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

    public boolean book(int start, int end) {
        Integer floorKey = calendar.floorKey(start);
        if (floorKey != null && calendar.get(floorKey) > start) return false;
        Integer ceilingKey = calendar.ceilingKey(start);
        if (ceilingKey != null && ceilingKey < end) return false;

        calendar.put(start, end);
        return true;
    }

    TreeMap<Integer, Integer> calendar;

    MyCalendar() {
        calendar = new TreeMap();
    }

    public boolean book(int start, int end) {
        Integer prev = calendar.floorKey(start),
                next = calendar.ceilingKey(start);
        if ((prev == null || calendar.get(prev) <= start) &&
                (next == null || end <= next)) {
            calendar.put(start, end);
            return true;
        }
        return false;
    }
https://leetcode.com/problems/my-calendar-i/discuss/109475/JavaC++-Clean-Code-with-Explanation

    TreeSet<int[]> books = new TreeSet<int[]>((int[] a, int[] b) -> a[0] - b[0]);

    public boolean book(int s, int e) {
        int[] book = new int[] { s, e }, floor = books.floor(book), ceiling = books.ceiling(book);
        if (floor != null && s < floor[1]) return false; // (s, e) start within floor
        if (ceiling != null && ceiling[0] < e) return false; // ceiling start within (s, e)
        books.add(book);
        return true;
    }

X.
https://leetcode.com/problems/my-calendar-i/discuss/109493/A-much-smarter-binarySearch-algorithm

// algorithm 2017/11/19: keep intervals sorted, but we do not really care whether it is an accurate match; so long there is an overlapping, we deem the two intervals equals
public MyCalendar() {
    
}

public boolean book(int start, int end) {
    assert start < end;
    Interval interval = new Interval(start, end-1);
    int foundIndex = Collections.binarySearch(entries, interval);
    if (foundIndex >= 0) {
        return false;
    }
    // insert and merge
    int insertPos = -(foundIndex+1);//\\
    entries.add(insertPos, interval);
    // optionally merge
    return true;
}

private List<Interval> entries = new ArrayList<>();

class Interval implements Comparable<Interval> {
    public Interval(int start, int end) {
        this.start = start;
        this.end   = end;
    }
    public int compareTo(Interval anotherInterval) {
        if (this.end < anotherInterval.start) {
            return -1;
        } else if (this.start > anotherInterval.end) {
            return 1;
        } else {
            return 0;       // intervals are equal so long they overlap
        }
    }
    
    int start;  // inclusive
    int end;    // inclusive
}

// sort by end

private List<Interval> intervals = new ArrayList<>();

public MyCalendar() {

}

public boolean book(int start, int end) {

if (intervals.isEmpty()) {

intervals.add(new Interval(start, end));

return true;

}

int pos = Collections.binarySearch(intervals, new Interval(start, end));

if (pos >= 0) {

return false;

}

pos = -pos - 1;

// defensive programming

// even if think it may be always >=0, it's better to add the extra condition,

// as it may be not that case

if (pos - 1 >= 0 && intervals.get(pos - 1).end > start) {

// not >= error prone

return false;

}

if (pos < intervals.size() && intervals.get(pos).start < end) {

// not >= error prone

return false;

}

if (pos < intervals.size()) { // not -1

intervals.add(pos, new Interval(start, end));

} else {

intervals.add(new Interval(start, end));

}

return true;

}

private static class Interval implements Comparable<Interval> {

public final int start, end;

public Interval(int start, int end) {

super();

this.start = start;

this.end = end;

}

@Override

public String toString() {

return "Interval [start=" + start + ", end=" + end + "]";

}

@Override

public int compareTo(Interval other) {

// if (this.end == other.end) {

// // \\

// return Integer.compare(this.start, other.start);

// }

return Integer.compare(this.end, other.end);

}

}

• Time Complexity: $O(N^2)$, where $N$ is the number of events booked. For each new event, we process every previous event to decide whether the new event can be booked. This leads to $\sum_k^N O(k) = O(N^2)$complexity.
• Space Complexity: $O(N)$, the size of the calendar.

    List<int[]> calendar;

    MyCalendar() {
        calendar = new ArrayList();
    }

    public boolean book(int start, int end) {
        for (int[] iv: calendar) {
            if (iv[0] < end && start < iv[1]) return false;//\\
        }
        calendar.add(new int[]{start, end});
        return true;
    }


X. https://www.cnblogs.com/FannyChung/p/7896415.html

对于不能重合的事件，可以利用BST二叉搜索树，每个节点代表一个事件区间，如果要插入的部分全部在当前节点的左侧或者右侧，则左递归或者右递归，否则，插入失败。
如果是用循环实现，则需要保存插入节点的父节点以及是父节点的左子还是右子。循环实现的代码如下：

    class Node {//节点有起始结束时间和左右子节点
        public Node(int start, int end) {
            l = start;
            r = end;
        }

        int l, r;
        Node left, right;
    }

    Node root = null;

    public boolean book(int start, int end) {
        if (root == null) {
            root = new Node(start, end);
        } else {
            Node cur = root;
            Node pre = null;//父节点
            boolean leftTag = false;//记录该插入的节点是左子还是右子
            while (cur != null) {
                pre = cur;
                if (end <= cur.l) {//应该在当前节点的左侧，往左子递归
                    leftTag = true;
                    cur = cur.left;
                } else if (start >= cur.r) {//应该在当前节点的右侧，往右子递归
                    leftTag = false;
                    cur = cur.right;
                } else {// 有重叠，不应该插入，返回false
                    return false;
                }
            }
            if (leftTag) {//根据tag确定是父亲的左子还是右子
                pre.left = new Node(start, end);
            } else {
                pre.right = new Node(start, end);
            }
        }
        return true;
    }