当前位置:网站首页>力扣今日題-729. 我的日程安排錶 I

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

2022-07-06 02:26:00 抗爭的小青年

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。

Snipaste_2022-07-05_13-27-48

  • 判斷到第一個就找到了

Snipaste_2022-07-05_13-46-48

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

  • 中間插入

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

Snipaste_2022-07-05_13-51-22

先判斷,發現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的

原网站

版权声明
本文为[抗爭的小青年]所创,转载请带上原文链接,感谢
https://yzsam.com/2022/187/202207060225154920.html