Para encontrar todos los rangos de fechas superpuestas de una lista dada de intervalos de fecha de

Question

Tengo una lista de BookingDateRange donde BookingDateRange es:

public class BookingDateRange { 
     private Date fromDate; 
     private Date toDate; 

     //getters & setters of properties 
    } 

Requisito:

1. Necesito encontrar en su caso la fecha se superpone en la Lista de fecha de reservación date dateRangeList
2. En caso afirmativo, encuentre todos los intervalos de fechas que se superpongan, por ejemplo, List of String say overlappingDatePairs

Ejemplo1:

Input1:

dateRangeList [0] = 23 dec 2012- 27 de diciembre 2012

dateRangeList [1] = 14 diciembre 2012 hasta 25 diciembre 2012

dateRangeList [2] = 1 de enero de 2012 - 23 de enero de 2012

Salida1:

isOverlappingDates = true

overlappingDatePairs = [0_1]

Ejemplo 2:

INPUT2:

dateRangeList [0] = 23 dec 2012- 27 dic 2012

dateRangeList [1] = 1 de enero de 2012 - 23 de enero de 2012

Salida2:

isOverlappingDates = false

overlappingDatePairs = []

Mi Solución:

/** 
* Checks if any of the dates overlap. 
* 
* @param dateRangeList the date range list 
* @param overlappingDatePairs the overlapping date pairs where overlappingDatePair is stored in the format dateRange1_dateRange2 
* @return true, if any of the dates overlap. 
*/ 

public static boolean isOverlappingDates(
      List<BookingDateRange> dateRangeList, 
      List<String> overlappingDatePairs) { 

    boolean isOverlap = false; 

    for (int index1 = 0; index1 < dateRangeList.size(); index1++) { 
     for (int index2 = index1 + 1; index2 < dateRangeList.size(); index2++) { 

      // Overlap exists if (StartA <= EndB) and (EndA >= StartB) 

      Date startA = dateRangeList.get(index1).getFromDate(); 
      Date endA = dateRangeList.get(index1).getToDate(); 
      Date startB = dateRangeList.get(index2).getFromDate(); 
      Date endB = dateRangeList.get(index2).getToDate(); 

      boolean isStartABeforeEndB = (startA.compareTo(endB)) < 0; 
      boolean isEndAAfterStartB = (endA.compareTo(startB)) > 0; 

      boolean isCurrentPairOverlap = false; 

      isCurrentPairOverlap = isStartABeforeEndB && isEndAAfterStartB; 

      if (isCurrentPairOverlap) { 
       overlappingDatePairs.add(index1 + "_" + index2); 
       isOverlap = true; 
      } 
     } 

    } 
    return isOverlap; 

    } 

La complejidad de este enfoque es O (n^2). ¿Es posible una mejor complejidad? No se pudo llegar a un algoritmo con una mejor complejidad.

Encontré algunas soluciones en SO. Pero ninguno de ellos podría atender el requisito por completo.

Gracias, Shikha

Answer 1

Aquí está O (nlog (n)), o obviamente si hay muchas colisiones, es O (número de colisiones). Una empresa para la que solía trabajar usó algo similar a esto como una pregunta de entrevista.

private static class BookingTuple implements Comparable<BookingTuple> { 
    public final Date date; 
    public final boolean isStart; 
    public final int id; 
    public BookingTuple(Date date, boolean isStart, int id) { 
     this.date = date; 
     this.isStart = isStart; 
     this.id = id; 
    } 

    @Override 
    public int compareTo(BookingTuple other) { 
     int dateCompare = date.compareTo(other.date); 
     if (dateCompare != 0) { 
      return dateCompare; 
     } else { 
      if (!isStart && other.isStart) { 
       return -1; 
      } else if (isStart && !other.isStart) { 
       return 1; 
      } else { 
       return 0; 
      } 
     } 
    } 
} 

public static boolean isOverlappingDates(List<BookingDateRange> dateRangeList, List<String> overlappingDatePairs) { 
    List<BookingTuple> list = new ArrayList<BookingTuple>(); 
    for (int i = 0; i < dateRangeList.size(); i++) { 
     Date from = dateRangeList.get(i).getFromDate(); 
     Date to = dateRangeList.get(i).getToDate(); 
     list.add(new BookingTuple(from, true, i)); 
     list.add(new BookingTuple(to, false, i)); 
    } 

    Collections.sort(list); 

    boolean overlap = false; 

    HashSet<Integer> active = new HashSet<Integer>(); 
    for (BookingTuple tuple : list) { 
     if (!tuple.isStart) { 
      active.remove(tuple.id); 
     } else { 
      for (Integer n : active) { 
       overlappingDatePairs.add(n + "_" + tuple.id); 
       overlap = true; 
      } 
      active.add(tuple.id); 
     } 
    } 

    return overlap; 
} 

Answer 2

no creo que puedes hacerlo mejor ya que hay que comparar cada BookingDateRange con los demás ...

por lo que toma O(n) comparisons per element y tiene n elements

lo tanto n * n = O(n^2)

Answer 3

Mi solución cambiaría la complejidad de la memoria. Supone que el rango de fechas es relativamente limitado (no está mezclando fechas de 5000BC y 6000AD).

1 Crea un Map<String, List<Range>>.

2 Para cada uno de los rangos, elija la primera fecha y conviértala en GregorianCalendar. Obtenga la fecha en formato "aaaa/MM/dd" (o similar).

2a Si la cadena "yyyy/MM/dd" ya está en el mapa, agregue el nuevo rango a la lista.

2b Si no lo está, agregue la entrada con una nueva lista que contiene el rango.

2c Aumenta el calendario Gregorian al día. Repita hasta que se haya alcanzado la última fecha en el rango.

3 Repita para todos los rangos.

4 Listar las teclas del Mapa (si usó el formato "aaaa/MM/dd" la clasificación es trivial). Verifique el tamaño de la lista asociada.