Given a list of date ranges, find a date which occurs maximum times

Question

I have a list of Booking which contains startDate and endDate. I have to find the day which is the busiest in terms of bookings.

class Booking {
    Date startDate;
    Date endDate;
}

Example:

2016-10-12 to 2016-10-18
2016-10-11 to 2016-10-15
2016-10-13 to 2016-10-14
2016-10-12 to 2016-10-13

From these dates, it is obvious that 2016-10-13 was booked on all 4 times.

The solution that comes to my mind is:

• iterate through all the dates from minimum startDate to maximum endDate in the list
• keep a count of all number of bookings on all dates.
• finally, return the date having maximum count.

But this is not the efficient solution. How can I find busiest day efficiently?

Answer 1

You can convert each Booking object as an interval in the number line, and then consider the problem as the problem of finding the point on the number line which is contained by maximum number of the intervals.

You can convert the date to number just by appending the year, month and day values, like this:

2016-10-12 -> 20161012

Then you can follow along this technique. Here is what I did, without the parts of converting the Date to int:

class Main {
    public static int findBusiest (int[] starts, int[] ends) {
        Arrays.sort(starts);
        Arrays.sort(ends);
        int n = starts.length;

        int in = 1, max = 1, time = starts[0];
        int i = 1, j = 0;

        while (i < n && j < n) {
            if (starts[i] <= ends[j]) {
                in++;

                if (in > max) {
                    max = in;
                    time = starts[i];
                }
                i++;
            }
            else {
                in--;
                j++;
            }
        }

        return time;
    }

    public static void main(String[] args) {

        int[] starts = { 20161012, 20161011, 20161013, 20161012 };
        int[] ends = { 20161018, 20161015, 20161014, 20161013 };

        System.out.println(findBusiest(starts, ends));
    }
}

Outputs:

20161013