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; } } |
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).