Чтобы найти все перекрывающиеся диапазоны дат из заданного списка диапазонов дат

У меня есть список BookingDateRange, где BookingDateRange:

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

        //getters & setters of properties
   }

Requirement:

I need to find if any date overlaps in List of BookingDate say dateRangeList If yes, find all the date ranges pair which overlap say List of String say overlappingDatePairs

Example1:

Input1:

dateRangeList [0] = 23 декабря 2012 года - 27 декабря 2012 года

dateRangeList [1] = 14 декабря 2012 г. - 25 декабря 2012 г.

dateRangeList [2] = 1 января 2012 - 23 января 2012

Output1:

isOverlappingDates = true

overlappingDatePairs = [0_1]

Example2:

Input2:

dateRangeList [0] = 23 декабря 2012 года - 27 декабря 2012 года

dateRangeList [1] = 1 января 2012 - 23 января 2012

Выход2:

isOverlappingDates = false

overlappingDatePairs = []

My Solution :

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

    }

Сложность этого подхода O (n ^ 2). Возможна ли лучшая сложность? Не удалось получить алгоритм с большей сложностью.

Сталкивался с несколькими решениями в SO. Но никто из них не мог полностью удовлетворить это требование.

Спасибо, Shikha

Ответы на вопрос(3)

Ваш ответ на вопрос