Ich habe eine Liste mit BookingDateRange, in der BookingDateRange enthalten ist:

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

        //getters & setters of properties
   }

Anforderung:

Ich muss feststellen, ob sich ein Datum in der Liste der Buchungsdaten überschneidet. Sagen Sie dateRangeListWenn ja, suchen Sie alle Datumsbereichspaare, die sich überschneiden, z. B. Liste der Zeichenfolgen, z. B. overlappingDatePairs

Beispiel 1:

Input1:

dateRangeList [0] = 23. Dezember 2012 - 27. Dezember 2012

dateRangeList [1] = 14. Dezember 2012 - 25. Dezember 2012

dateRangeList [2] = 1. Januar 2012 - 23. Januar 2012

Output1:

isOverlappingDates = true

overlappingDatePairs = [0_1]

Beispiel2:

Input2:

dateRangeList [0] = 23. Dezember 2012 - 27. Dezember 2012

dateRangeList [1] = 1. Januar 2012 - 23. Januar 2012

Output2:

isOverlappingDates = false

overlappingDatePairs = []

Meine Lösung :

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

    }

Die Komplexität dieses Ansatzes ist O (n ^ 2). Ist eine bessere Komplexität möglich? Konnte nicht zu einem Algorithmus mit einer besseren Komplexität kommen.

Bin auf ein paar Lösungen bei SO gestoßen. Aber keiner von ihnen konnte die Anforderung vollständig erfüllen.

Danke, Shikha