## Friday, April 27, 2018

### LeetCode 729 - My Calendar I

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.
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)
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);//\\
// 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()) {
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
} else {
}
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;//\\
}
return true;
}