Per trovare tutti i intervalli di date sovrapposte da un determinato elenco di intervalli di date

Question

Ho una lista di BookingDateRange dove BookingDateRange è:

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

     //getters & setters of properties 
    } 

Requisito:

1. ho bisogno di trovare eventuali data si sovrappone in Elenco di BookingDate dice dateRangeList
2. In caso affermativo, trova tutte le coppie di intervalli di date che si sovrappongono, diciamo List of String dire overlappingDatePairs

Esempio1:

Input1:

dateRangeList [0] = 23 dicembre 2012- 27 dicembre 2012

dateRangeList [1] = 14 dic 2012 - 25 dicembre 2012

dateRangeList [2] = 1 gen 2012 - 23 gen 2012

Output1:

isOverlappingDates = true

overlappingDatePairs = [0_1]

Example2:

Input2:

dateRangeList [0] = 23 dicembre 2012- 27 dicembre 2012

dateRangeList [1] = 1 gennaio 2012 - 23 gennaio 2012

Output2:

isOverlappingDates = falsi

overlappingDatePairs = []

mia soluzione:

/** 
* 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 complessità di questo approccio è O (n^2). È possibile una migliore complessità? Impossibile arrivare a un algoritmo con una maggiore complessità.

Ho trovato alcune soluzioni in SO. Ma nessuno di loro poteva soddisfare completamente il requisito.

Grazie, Shikha

Answer 1

Ecco O (nlog (n)), o ovviamente se ci sono molte collisioni, è O (numero di collisioni). Una società per la quale lavoravo usava qualcosa di simile a questa come una domanda di intervista.

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

io non credo che si può fare di meglio, poiché è necessario confrontare ogni BookingDateRange con gli altri ...

quindi ci vuole O(n) comparisons per element e si ha n elements

quindi n * n = O(n^2)

Answer 3

La mia soluzione sarebbe scambiare complessità per la memoria. Si presuppone che l'intervallo di date sia relativamente limitato (non si mischiano date da 5000BC e 6000AD).

1 Creare uno Map<String, List<Range>>.

2 Per ciascuno degli intervalli, selezionare la prima data e convertirla in GregorianCalendar. Ottieni la data nel formato "aaaa/MM/gg" (o simile).

2a Se la stringa "yyyy/MM/dd" è già nella Mappa, aggiungere la nuova Intervallo all'elenco.

2b In caso contrario, aggiungere la voce con una nuova lista contenente l'intervallo.

2c Aumentare il GregorianCalendar al giorno. Ripeti fino al raggiungimento della data ultima nell'intervallo.

3 Ripetere per tutte le gamme.

4 Elenca le chiavi della mappa (se hai utilizzato l'ordinamento in formato "aaaa/MM/gg" è banale). Controlla la dimensione dell'elenco associato.