Eu tenho uma lista de BookingDateRange onde BookingDateRange é:

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

        //getters & setters of properties
   }

Requerimento:

Eu preciso encontrar se qualquer data sobrepõe na lista de BookingDate digamos dateRangeListEm caso afirmativo, localize todos os pares de intervalos de datas que se sobrepõem, como diz Lista de Cadeia de caracteres, dizem overlappingDatePairs

Exemplo 1:

Input1:

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

dateRangeList [1] = 14 de dezembro de 2012 - 25 de dezembro de 2012

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

Saída1:

isOverlappingDates = true

overlappingDatePairs = [0_1]

Example2:

Entrada2:

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

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

Output2:

isOverlappingDates = false

overlappingDatePairs = []

Minha solução:

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

    }

A complexidade dessa abordagem é O (n ^ 2). É uma melhor complexidade possível? Não foi possível chegar a um algoritmo com uma melhor complexidade.

Entrei em algumas soluções na SO. Mas nenhum deles poderia atender ao requisito completamente.

Obrigado, shikha