Categorías
Algorithms

LeetCode – Mi calendario II (Java)

Implemente una clase MyCalendarTwo para almacenar sus eventos. Se puede agregar un nuevo evento si agregar el evento no causa una reserva triple.

Tu clase tendrá un método, book (int start, int end). Formalmente, esto representa una reserva en el intervalo semiabierto[inicio, fin), el rango de números reales x tal que inicio <= x

Example:

MyCalendar();
MyCalendar.book(10, 20); // returns true
MyCalendar.book(50, 60); // returns true
MyCalendar.book(10, 40); // returns true
MyCalendar.book(5, 15); // returns false
MyCalendar.book(5, 10); // returns true
MyCalendar.book(25, 55); // returns true

Solución Java

Esta es una versión más complicada de My Calendar I, en la que solo nos importa si ya se usa un intervalo de tiempo. Para este problema, podemos agregar otra lista para rastrear los intervalos reservados dobles.

class MyCalendarTwo {
    ArrayList<int[]> single = null;
    ArrayList<int[]> overlap = null;
 
    public MyCalendarTwo() {
        single = new ArrayList<>();
        overlap = new ArrayList<>();
    }
 
    public boolean book(int start, int end) {
        for (int[] itv : overlap) {
            if (end > itv[0] && start < itv[1]) {
                return false;
            }
        }
 
        for (int[] itv : single) {
            if (end > itv[0] && start < itv[1]) {
                overlap.add(new int[]{Math.max(itv[0], start), Math.min(itv[1], end)});
            }
        }
 
        single.add(new int[]{start, end});
 
        return true;
    }
}
  LeetCode - Promedio móvil de flujo de datos (Java)

La complejidad del tiempo es O (N ^ 2) ya que cada operación del libro itera sobre todos los intervalos existentes. La complejidad del espacio es O (N).

Por Programación.Click

Más de 20 años programando en diferentes lenguajes de programación. Apasionado del code clean y el terminar lo que se empieza. ¿Programamos de verdad?

Deja una respuesta

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *