力扣今日題-729. 我的日程安排錶 I

729. 我的日程安排錶 I

二分

1. 先將所有已經預定的序列進行排序，然後依次遍曆區間，看某個區間的left1，是否大於end

12會和3,5,10進行比較，這是會發現沒有比它大的區間，這時就該考慮往它們後面插入了。

• 未找到：那就和最後一個區間的right1比較,看最後一個區間的right1是否小於插入區間的start,如果可以就返回ture，否則就返回false

12會和最後一個元素的15進行比較，發現15是大於12的，返回false.

而17先和3，7，10進行比較，發現都比它們大，所以考慮往後面放置，然後20和15比較，發現20大於15，返回true。

• 判斷到第一個就找到了

一判斷，就發現end要小於最小的left1，所以可以插入，就返回true

• 中間插入

中間區間，找到last的上一個區間pre[left2,right2],若right2要大於start，則說明有交集，返回false，否則返回true。

先判斷，發現10==10,停下來判斷7，一看7<8有交集，返回false。

比如[9,10]這是一個正確的例子，發現 10 =- 10，停下來判斷，一看9> 8,返回true。

• 代碼：

    List<int[]> data;

    public MyCalendar() {
    
        data = new ArrayList<>();
    }

    public boolean book(int start, int end) {
    
        if (data.size() == 0) {
    
            data.add(new int[]{
    start, end});
            return true;
        }
        data.sort(Comparator.comparingInt(o -> o[0]));
        int left = 0, right = data.size() - 1;
        //找到第一個start >= end的區間
        int ans = -1;
        while (left <= right) {
    
            int mid = left + (right - left) / 2;
            if (data.get(mid)[0] >= end) {
    
                ans = mid;
                right = mid - 1;
            } else {
    
                left = mid + 1;
            }
        }
        //沒有找到 和最後一個區間比較
        if (ans == -1) {
    
            int[] ints = data.get(data.size() - 1);
            if (ints[1] > start) {
    
                return false;
            }
        } else if (ans != 0) {
    
            //不是第一個區間，如果是第一個區間則可以直接插入
            int[] pre = data.get(ans - 1);
            if (pre[1] > start) {
    
                return false;
            }
        }
        data.add(new int[]{
    start, end});
        return true;
    }

直接遍曆

class MyCalendar {
    
    // 定義一個booked
    List<int[]> booked;
    public MyCalendar() {
    
        booked = new ArrayList<int[]>();
    }
    
    public boolean book(int start, int end) {
    
        for(int[] arr : booked){
    
            int l = arr[0] ,r = arr[1];
            //第二種情况
            if(l < end && start < r){
    
                return false;
            }
        }
        booked.add(new int[]{
    start,end});
        return true;
    }
}

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

[s1,e1)和[s2,e2)，沒有交集滿足s1>e2或者s2>e1，反之則說明兩者回產生交集。

思路三

轉變一下思維，可以把重疊這個概念擴展到廣義的相等概念，即一旦重疊就代錶兩個元素相等，那麼這就簡單了，set專門用來去重存儲。 那麼HashSet和TreeSet用哪個呢？ 首先HashSet去重是根據對象的哈希值，由於我們要存儲的是int[]類型的，我們在寫代碼的時候是要根據start和end來創建它，那麼它們的哈希值基本不同，也就是說就算兩個int[]裏面的值完全一樣，但是哈希值不同，HashSet也會把它們存進去。 由於我們把重疊看作是廣義上的相等，那麼就需要定義一個比較器要區分它們的是否廣義相等，而TreeSet支持自定義比較器，而且根據比較器返回的值進行排序，非常符合我們的需求。

class MyCalendar {
    
    //定義一個TreeSet
    TreeSet<int[]> calendars;

    public MyCalendar() {
    
        calendars = new TreeSet<>((a, b) -> {
    
            if(a[1] <= b[0])
                return -1;
            else if(a[0] >= b[1])
                return 1;
            else
                return 0;
        });
    }
    
    public boolean book(int start, int end) {
    
        int[] e = new int[]{
    start, end};
        return calendars.add(e);
    }
}
/** * Your MyCalendar object will be instantiated and called as such: * MyCalendar obj = new MyCalendar(); * boolean param_1 = obj.book(start,end); */

拓展

TreeSet簡介：有序，不可重複，紅黑樹，基於Treemap實現，自定義排序等特點。

TreeSet 是一個有序的集合，它的作用是提供有序的Set集合。它繼承於AbstractSet抽象類，實現了NavigableSet, Cloneable, java.io.Serializable接口。
TreeSet 繼承於AbstractSet，所以它是一個Set集合，具有Set的屬性和方法。
TreeSet 實現了NavigableSet接口，意味著它支持一系列的導航方法。比如查找與指定目標最匹配項。
TreeSet 實現了Cloneable接口，意味著它能被克隆。
TreeSet 實現了java.io.Serializable接口，意味著它支持序列化。
TreeSet是基於TreeMap實現的。TreeSet中的元素支持2種排序方式：自然排序 或者 根據創建TreeSet 時提供的 Comparator 進行排序。這取决於使用的構造方法。
TreeSet為基本操作（add、remove 和 contains）提供受保證的 log(n) 時間開銷。
另外，TreeSet是非同步的。 它的iterator 方法返回的迭代器是fail-fast的