731. My Calendar II

LeetCode medium original: C# #csharp #intervals #leetcode #math #medium

Der Aufgabentext wird für die gewählte Sprache aus dem Russischen übersetzt. Code bleibt unverändert.

LeetCode Static

Вы создаете программу для использования в качестве календаря. Мы можем добавить новое событие, если его добавление не приведет к тройному бронированию. Тройное бронирование происходит, когда три события имеют некоторое непустое пересечение (т.е, Событие можно представить в виде пары целых чисел start и end, которая представляет собой бронирование на полуоткрытом интервале [start, end), диапазоне вещественных чисел x таких, что start <= x < end. Implementierung класса MyCalendarTwo: MyCalendarTwo() Инициализирует объект календаря. boolean book(int start, int end) returns true, если событие может быть успешно добавлено в календарь, не вызывая тройного бронирования. В противном случае returnsся false и событие не добавляется в календарь.

Beispiel:

Input

["MyCalendarTwo", "book", "book", "book", "book", "book", "book"]

[[], [10, 20], [50, 60], [10, 40], [5, 15], [5, 10], [25, 55]]

Output

[null, true, true, true, false, true, true]

C# Lösung

zugeordnet/original

using System;
using System.Collections.Generic;
public class MyCalendarTwo {
    private List<(int, int)> events;
    private List<(int, int)> overlaps;
    public MyCalendarTwo() {
        events = new List<(int, int)>();
        overlaps = new List<(int, int)>();
    }
    public bool Book(int start, int end) {
        foreach (var (os, oe) in overlaps) {
            if (start < oe && end > os) {
                return false;
            }
        }
        foreach (var (es, ee) in events) {
            if (start < ee && end > es) {
                overlaps.Add((Math.Max(start, es), Math.Min(end, ee)));
            }
        }
        events.Add((start, end));
        return true;
    }
}

C++ Lösung

Auto-Entwurf, vor dem Einreichen prüfen

#include <bits/stdc++.h>
using namespace std;

// Auto-generated C++ draft from the C# solution. Review containers, LINQ and helper types before submit.
public class MyCalendarTwo {
    private List<(int, int)> events;
    private List<(int, int)> overlaps;
    public MyCalendarTwo() {
        events = new List<(int, int)>();
        overlaps = new List<(int, int)>();
    }
    public bool Book(int start, int end) {
        foreach (var (os, oe) in overlaps) {
            if (start < oe && end > os) {
                return false;
            }
        }
        foreach (var (es, ee) in events) {
            if (start < ee && end > es) {
                overlaps.push_back((max(start, es), min(end, ee)));
            }
        }
        events.push_back((start, end));
        return true;
    }
}

Java Lösung

zugeordnet/original

import java.util.ArrayList;
import java.util.List;

public class MyCalendarTwo {
    private List<int[]> events;
    private List<int[]> overlaps;

    public MyCalendarTwo() {
        events = new ArrayList<>();
        overlaps = new ArrayList<>();
    }

    public boolean book(int start, int end) {
        for (int[] overlap : overlaps) {
            if (start < overlap[1] && end > overlap[0]) {
                return false;
            }
        }
        for (int[] event : events) {
            if (start < event[1] && end > event[0]) {
                overlaps.add(new int[]{Math.max(start, event[0]), Math.min(end, event[1])});
            }
        }
        events.add(new int[]{start, end});
        return true;
    }
}        this.events.push([start, end]);
        return true;
    }
}

JavaScript Lösung

zugeordnet/original

class MyCalendarTwo {
    constructor() {
        this.events = [];
        this.overlaps = [];
    }

    book(start, end) {
        for (let [os, oe] of this.overlaps) {
            if (start < oe && end > os) {
                return false;
            }
        }
        for (let [es, ee] of this.events) {
            if (start < ee && end > es) {
                this.overlaps.push([Math.max(start, es), Math.min(end, ee)]);
            }
        }
        this.events.push([start, end]);
        return true;
    }
}

Python Lösung

zugeordnet/original

class MyCalendarTwo:
    def __init__(self):
        self.events = []
        self.overlaps = []

    def book(self, start, end):
        for os, oe in self.overlaps:
            if start < oe and end > os:
                return False
        for es, ee in self.events:
            if start < ee and end > es:
                self.overlaps.append((max(start, es), min(end, ee)))
        self.events.append((start, end))
        return True

Go Lösung

zugeordnet/original

package main

type MyCalendarTwo struct {
    events   [][2]int
    overlaps [][2]int
}

func Constructor() MyCalendarTwo {
    return MyCalendarTwo{}
}

func (this *MyCalendarTwo) Book(start int, end int) bool {
    for _, overlap := range this.overlaps {
        if start < overlap[1] && end > overlap[0] {
            return false
        }
    }
    for _, event := range this.events {
        if start < event[1] && end > event[0] {
            this.overlaps = append(this.overlaps, [2]int{max(start, event[0]), min(end, event[1])})
        }
    }
    this.events = append(this.events, [2]int{start, end})
    return true
}

func max(a, b int) int {
    if a > b {
        return a
    }
    return b
}

func min(a, b int) int {
    if a < b {
        return a
    }
    return b
}

Algorithm

Создайте два списка: один для отслеживания всех событий, второй для отслеживания пересечений. подпоследовательностей.

При добавлении нового события сначала проверьте, не пересекается ли оно с любыми существующими пересечениями.

Если пересечение не обнаружено, добавьте новое событие и обновите список пересечений при необходимости.

😎

Stellen zu dieser Aufgabe

aktive Stellen with overlapping task tags are angezeigt.

Alle Stellen

Es gibt noch keine aktiven Stellen.