关于算法:LC729-My-Calendar-I

https://leetcode.com/problems…

Medium
Google, Uber, Amazon, Twitch

class MyCalendar {private List<int[]> events;

    public MyCalendar() {events = new ArrayList<>();
        // 题目有输出限度，0 <= start < end <= 10^9
        // 能够减少左右边界，不便计算
        events.add(new int[]{-1, 0});
        events.add(new int[]{1000000001, 1000000001});
    }
    public boolean book(int start, int end) {
        // 应用二分法查找能够插入的地位
        int left = 0, right = events.size() - 1;
        while (left + 1 < right) {int mid = left + (right - left) / 2;
            int[] event = events.get(mid);
            if (start == event[0])  return false; // 如果 start 等于以后 event 的 start，那么必定有抵触，间接返回 false
            if (start < event[0])   right = mid;  // 若 start 小于以后 event 的 start，那么要往左边找
            else                    left = mid;   // 若 start 大于以后 event 的 start，那么往右找
        }
        // 最终要安顿插入的 event 就是坐落在 left 和 right 之间，看是否能插入
        if (start >= events.get(left)[1] && end <= events.get(right)[0]) {
            // 能够插入
            events.add(right, new int[]{start, end});
            return true;
        }
        // 不能插入
        return false;
    }
}