Mam listę BookingDateRange gdzie BookingDateRange to:

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

        //getters & setters of properties
   }

Wymaganie:

Muszę się dowiedzieć, czy jakaś data pokrywa się z Listą rezerwacjiData powiedzieć dateRangeListJeśli tak, znajdź wszystkie pary zakresów dat, które nakładają się, powiedzmy List String powiedz overlappingDatePairs

Przykład 1:

Input1:

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

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

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

Wyjście1:

isOverlappingDates = true

overlappingDatePairs = [0_1]

Przykład2:

Input2:

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

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

Wyjście2:

isOverlappingDates = false

overlappingDatePairs = []

Moje 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 podejścia 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 spełnić tego wymogu.

Dzięki, Shikha