znaleźć wszystkie date pokrywających się zakresów z danej listy zakresy dat

Question

Mam listę BookingDateRange gdzie BookingDateRange jest:

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

     //getters & setters of properties 
    } 

Wymagania:

1. Muszę znaleźć ewentualne data pokrywa się na liście BookingDate podaj dateRangeList
2. Jeśli tak, znajdź wszystkie pary zakresów dat, które się pokrywają, powiedz Lista ciągów mówi, że zachodzą na siebieDataPairs

Przykład1:

input1:

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

dateRangeList [1] = 14 grudnia 2012 - 25 grudnia 2012

dateRangeList [2] = 1 stycznia 2012 r. - 23 stycznia 2012 r.

Wyjście 1:

isOverlappingDates = true

overlappingDatePairs = [0_1]

Przykład2:

input2:

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

dateRangeList [1] = 1 stycznia 2012 r. - 23 stycznia 2012 r.

OUTPUT2:

isOverlappingDates = fałszywe

overlappingDatePairs = []

Proponowane rozwiązanie:

/** 
* 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; 

    } 

złożoność tego rozwiązania jest to O (N^2). Czy możliwa jest lepsza złożoność? Nie można uzyskać algorytmu o większej złożoności.

Znalazłem kilka rozwiązań w SO. Ale żaden z nich nie był w stanie całkowicie zaspokoić tego wymogu.

Dzięki Shikha

Answer 1

Oto O (nlog (n)), lub oczywiście, jeśli występuje wiele kolizji, jest to O (liczba kolizji). Firma, w której kiedyś pracowałem, użyła czegoś podobnego do pytania na rozmowę kwalifikacyjną.

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

Nie sądzę, można to zrobić lepiej, ponieważ trzeba porównać każdy BookingDateRange z innymi ...

więc zajmuje O(n) comparisons per element i masz n elements

dlatego n * n = O(n^2)

Answer 3

Moje rozwiązanie zamieniłbym złożoności dla pamięci. Zakłada się, że zakres dat jest względnie ograniczony (nie mieszacie dat z 5000BC i 6000AD). Stwórz Map<String, List<Range>>.

2 Dla każdego z zakresów wybierz pierwszą datę i przekonwertuj ją na GregorianCalendar. Pobierz datę w formacie "rrrr/MM/dd" (lub podobny).

2a Jeśli ciąg "yyyy/MM/dd" już znajduje się na mapie, dodaj nowy zakres do listy.

2b Jeśli nie jest, dodaj wpis z nową listą zawierającą zakres.

2c Zwiększyć liczbę kalendarza gregoriańskiego dziennie. Powtarzaj aż do osiągnięcia ostatniej daty w zakresie.

3 Powtórz dla wszystkich zakresów.

4 Wymień klawisze mapy (jeśli użyłeś sortowania "yyyy/MM/dd", to jest to proste). Sprawdź rozmiar powiązanej listy.