729. My Calendar I 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
class MyCalendar {

    private static class Interval {
        private final int start;
        private final int end;

        public Interval(int start, int end) {
            // [start, end)
            this.start = start;
            this.end = end;
        }
    }

    private final List<Interval> intervalList;

    public MyCalendar() {
        this.intervalList = new ArrayList<>();
    }

    public boolean book(int start, int end) {
        if (intervalList.isEmpty()) {
            intervalList.add(new Interval(start, end));
            return true;
        }

        int insertIndex = findInsertIndex(start);
        if (insertIndex == intervalList.size()) {
            // 在最右侧插入
            if (start < intervalList.get(intervalList.size() - 1).end) {
                return false;
            } else {
                intervalList.add(new Interval(start, end));
                return true;
            }
        } else if (insertIndex == 0) {
            // 在最左侧插入
            if (end > intervalList.get(0).start) {
                return false;
            } else {
                intervalList.add(0, new Interval(start, end));
                return true;
            }
        } else {
            // 在中间插入
            Interval leftInterval = intervalList.get(insertIndex - 1);
            Interval rightInterval = intervalList.get(insertIndex);
            if (start < leftInterval.end || end > rightInterval.start) {
                return false;
            } else {
                intervalList.add(insertIndex, new Interval(start, end));
                return true;
            }
        }
    }

    private int findInsertIndex(int start) {
        int left = 0, right = intervalList.size() - 1;
        while (left <= right) {
            int mid = (left + right) >>> 1;
            int midStart = intervalList.get(mid).start;
            if (midStart < start) {
                left = mid + 1;
            } else if (midStart > start) {
                right = mid - 1;
            } else {
                return mid;
            }
        }

        return left;
    }

}

References

729. My Calendar I
剑指 Offer II 058. 日程表