To find all the overlapping date ranges from a given list of Date Ranges

Question

I have a List of BookingDateRange where BookingDateRange is :

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

        //getters & setters of properties
   }

Requirement:

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

Example1:

Input1:

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

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

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

Output1:

isOverlappingDates = true

overlappingDatePairs = [0_1]

Example2:

Input2:

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

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

Output2:

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;

    }

The complexity of this approach is O(n ^2). Is a better complexity possible ? Could not arrive at an algorithm with a better complexity.

Did come across a few solutions at SO. But none of them could cater to the requirement completely.

Thanks, Shikha

Answer 1

Here's O(nlog(n)), or obviously if there are lots of collisions, it's O(number of collisions). A company I used to work for used something similar to this as an interview question.

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

I don't think you can do better since you have to compare each BookingDateRange with the others...

So it takes O(n) comparisons per element and you have n elements

therefore n * n = O(n^2)