Déduisez la question d'aujourd'hui - 729. Mon emploi du temps I

729. Mon emploi du temps I

Deux points

1. Triez d'abord toutes les séquences déjà programmées,Puis traversez l'intervalle à tour de rôle,Regarde dans une section.left1,Est - ce plus grand queend

12Et3,5,10Comparer,Il n'y a pas d'intervalle plus grand,Il est temps d'envisager d'insérer.

• Non trouvé：C'est avec le dernierright1Comparaison,Regardez la dernière sectionright1Est inférieur à la plage d'insertionstart,Si possible, retournez àture,Sinon, retournez àfalse

12Et le dernier élément15Comparer,Découverte15Est supérieur à12De,Retourfalse.

Et17D'abord.3,7,10Comparer,Les résultats sont plus grands qu'eux,Alors, envisagez de placer,Et puis20Et15Comparaison,Découverte20Plus grand que15,Retourtrue.

• J'ai trouvé le premier

I) Jugement ,Je l'ai trouvé.end Plus petit que le plus petit left1,Pour pouvoir insérer,Je revienstrue

• Insertion au milieu

Intervalle intermédiaire,Trouverlast La section précédente de pre[left2,right2],Siright2Plus grand questart, Il y a intersection ,Retourfalse,Sinon, retournez àtrue.

Juge d'abord,Découverte10==10, Arrête de juger 7,Regarde.7<8Avec intersection,Retourfalse.

Par exemple,[9,10] C'est un bon exemple ,Découverte 10 =- 10, Arrête de juger ,Regarde.9> 8,Retourtrue.

• Code：

    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;
        //Trouver le premierstart >= endIntervalle de
        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;
            }
        }
        //Je n'ai pas trouvé  Comparé au dernier intervalle 
        if (ans == -1) {
    
            int[] ints = data.get(data.size() - 1);
            if (ints[1] > start) {
    
                return false;
            }
        } else if (ans != 0) {
    
            // Pas la première section , Si c'est le premier intervalle, il peut être inséré directement 
            int[] pre = data.get(ans - 1);
            if (pre[1] > start) {
    
                return false;
            }
        }
        data.add(new int[]{
    start, end});
        return true;
    }

Directement à travers

class MyCalendar {
    
    // Définir unbooked
    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];
            //Dans le deuxième cas
            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)Et[s2,e2), Pas d'intersection satisfaisante s1>e2Ous2>e1, Inversement, cela signifie que les deux se croisent en arrière .

Pensée 3

Changez d'avis , Le concept de chevauchement peut être étendu au concept général d'égalité , C'est - à - dire qu'une fois superposés, les deux éléments sont égaux , Alors c'est simple ,set Spécialement conçu pour le déstockage . AlorsHashSetEtTreeSetAvec lequel?？ Tout d'abord,HashSet La dé - duplication est basée sur la valeur de hachage de l'objet , Parce que ce que nous stockons est int[]Type, Nous écrivons le Code en fonction de startEtendPour le créer, Donc leurs valeurs de hachage sont fondamentalement différentes , Ce qui veut dire que même si deux int[] Les valeurs sont exactement les mêmes , Mais les valeurs de hachage sont différentes ,HashSet Et les mettre dans . Parce que nous considérons le chevauchement comme une égalité au sens large , Il est donc nécessaire de définir un comparateur pour les distinguer de l'égalité généralisée ,EtTreeSet Prise en charge des comparateurs personnalisés , Et trier en fonction des valeurs retournées par le Comparateur , Très bien adapté à nos besoins .

class MyCalendar {
    
    //Définir unTreeSet
    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); */

Développement

TreeSetIntroduction：Ordre.,Non reproductible,Arbre Rouge et noir,Basé surTreemapRéalisation, Caractéristiques telles que le tri personnalisé .

TreeSet Est une collection ordonnée,Son rôle est d'assurer l'ordreSetEnsemble.Il est hérité deAbstractSetClasse abstraite,C'est fait.NavigableSet, Cloneable, java.io.SerializableInterface.
TreeSet Hérité deAbstractSet,Donc C'est unSetEnsemble,AvecSetPropriétés et méthodes de.
TreeSet C'est fait.NavigableSetInterface,Cela signifie qu'il supporte une gamme de méthodes de navigation.Comme trouver la meilleure correspondance avec la cible spécifiée.
TreeSet C'est fait.CloneableInterface,Ça veut dire qu'il peut être cloné.
TreeSet C'est fait.java.io.SerializableInterface,Cela signifie qu'il supporte la sérialisation.
TreeSetEst basé surTreeMapRéalisé.TreeSetÉléments pris en charge dans2Trier par：Ordre naturel Ou Selon la créationTreeSet Fourni à Comparator Trier.Cela dépend de la méthode de construction utilisée.
TreeSet Pour les opérations de base （add、remove Et contains） Fournir une garantie log(n) Dépenses de temps.
En plus,TreeSetEst asynchrone. C'est...iterator L'Itérateur retourné par la méthode estfail-fastDe