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

Answer 2

1. for simplicity, give each date their index (for example min date has index 0, the next day 1 and so on), and initialize array filled with zeros
2. iterate through all ranges and for start date index increment element in array, and decrement for the end date. (for example if some date d meets 3 times as start of the range and 5 time as the end of the range, there should be -2)
3. now, iterate through all dates from the beginning of the array, and add current element to your counter (basically, the value of counter at the date d, is how often it's inside ranges)
4. the answer is the max counter value

Algorithm works O(n) where n is the number of days between minDate and maxDate

PS. Solution mentioned by Patrick Parker in this post also works, but it will require O(m * log(m)) time, where m is the number of ranges. So you should choose solution depending on task specifications.

Answer 3

I would like to point out a property which might set you in the right direction.

The most frequent day(s) will either be an endpoint (start or end date), or they will be tied with an endpoint.

So if it is enough to find one day out of the tied days, you need only to consider days which fall on an endpoint.

Now, how will you increment the frequency for each end point reliably? By processing in order. But it is not enough to process start and end in order of start. starts and ends must both be considered in date order.

Answer 4

Well it is quite ugly, but we can do it using stream if you have a List of Booking

class Booking {
      LocalDate start;
      LocalDate end;
}

and we have a List

List<Booking> bookings = new ArrayList<>();
bookings.add(new Booking(LocalDate.of(2016, 10, 12),LocalDate.of(2016, 10, 18)));
bookings.add(new Booking(LocalDate.of(2016, 10, 11),LocalDate.of(2016, 10, 15)));
bookings.add(new Booking(LocalDate.of(2016, 10, 13),LocalDate.of(2016, 10, 14)));
bookings.add(new Booking(LocalDate.of(2016, 10, 12),LocalDate.of(2016, 10, 13)));

Now we can iterate over the list and for each booking get all the dates from start to end:

Stream<LocalDate> dateRanges = bookings.stream().flatMap(booking ->
        Stream.iterate(booking.start, d -> d.plusDays(1))
                .limit(ChronoUnit.DAYS.between(booking.start, booking.end) + 1)
);

We have all the dates, let's count how many times each date appear in the new stream.

Map<LocalDate, Long> datesFrequency = dateRanges.peek(System.out::println).
collect(Collectors.groupingBy(Function.identity(), Collectors.counting()));

and finally let's find the maxim - the most frequent date:

Optional<Map.Entry<LocalDate, Long>> mostFrequent = datesFrequency.entrySet().
stream().max((o1, o2) -> o1.getValue().compareTo(o2.getValue()));

In this case result will be Optional[2016-10-13=4];

Answer 5

For every {startDate, endDate} record generate two tuples {startDate,'start'}, {endDate, 'end'}. Sort these on the date first, and the second value second, making sure that end goes after start. (As I understand the intervals are inclusive, so you don't want to discount the ending reservation before accounting for the one that starts on the day that the previous one ends).

Then go over the tuples in the order as described above, incrementing a counter with each start, decrementing with each end, and keeping track of the maximum so far. The maximum is the most booked date.

Complexity is O(n*log(n)).

Answer 6

Whilst this may not be the most efficient way to do it, unless you're working with millions of dates, this will be quite fast. I added a few thousand dates in the example below and it did not take long on my system.

import java.text.ParseException;
import java.text.SimpleDateFormat;
import java.util.ArrayList;
import java.util.Calendar;
import java.util.Collections;
import java.util.Date;
import java.util.HashSet;

public class Days {
    Days() {
        long startTime = System.nanoTime();
        SimpleDateFormat ft = new SimpleDateFormat ("yyyy-MM-dd");
        ArrayList<Booking> dates = new ArrayList<Booking>();
        try {
            dates.add(new Booking(ft.parse("2016-10-14"), ft.parse("2016-10-18")));
            dates.add(new Booking(ft.parse("2016-11-11"), ft.parse("2018-12-15")));
            dates.add(new Booking(ft.parse("2016-10-13"), ft.parse("2016-10-14")));
            dates.add(new Booking(ft.parse("2016-10-5"), ft.parse("2016-10-13")));
            dates.add(new Booking(ft.parse("2016-10-12"), ft.parse("2020-10-13")));
            dates.add(new Booking(ft.parse("2016-10-10"), ft.parse("2018-10-13")));
            dates.add(new Booking(ft.parse("2015-10-12"), ft.parse("2016-11-13")));
            dates.add(new Booking(ft.parse("2016-09-12"), ft.parse("2016-12-13")));
            dates.add(new Booking(ft.parse("2016-08-12"), ft.parse("2016-10-18")));
            dates.add(new Booking(ft.parse("2016-10-01"), ft.parse("2016-10-26")));
            dates.add(new Booking(ft.parse("2016-02-03"), ft.parse("2016-10-28")));
            dates.add(new Booking(ft.parse("2016-10-04"), ft.parse("2016-12-28")));
            dates.add(new Booking(ft.parse("2015-10-05"), ft.parse("2056-10-16")));
            dates.add(new Booking(ft.parse("2012-10-12"), ft.parse("2016-10-14")));
            dates.add(new Booking(ft.parse("2011-10-12"), ft.parse("2017-02-18")));
            dates.add(new Booking(ft.parse("2016-10-06"), ft.parse("2018-10-13")));
            dates.add(new Booking(ft.parse("2016-10-12"), ft.parse("2019-10-13")));
        } catch (ParseException e) {
            e.printStackTrace();
        }

        ArrayList<Date> datesMult = new ArrayList<Date>();

        for(Booking b : dates) {
            datesMult.addAll(b.getDates());
        }

        HashSet<Date> datesOnce = new HashSet<Date>(datesMult);

        int highestCount = -1;
        Date mostUsed = new Date();

        for(Date d : datesOnce) {
            int count = Collections.frequency(datesMult, d);
            if(count > highestCount) {
                highestCount = count;
                mostUsed = d;
            }
        }

        System.out.println("The most common used date is " + ft.format(mostUsed) + " and it got used " + highestCount + " times");
        long endTime = System.nanoTime();

        long duration = (endTime - startTime);
        System.out.println("This took " + duration + " nanoseconds");
    }

    private class Booking {
        Date startDate;
        Date endDate;

        Booking(Date d1, Date d2) {
            startDate = d1;
            endDate = d2;
        }

        public ArrayList<Date> getDates() {
            ArrayList<Date> d = new ArrayList<Date>();
            d.add(startDate);
            Calendar c = Calendar.getInstance();
            while(true) {
                c.setTime(startDate);
                c.add(Calendar.DATE, 1);  // number of days to add
                startDate = c.getTime();
                if(startDate.compareTo(endDate) == -1) {
                    d.add(startDate);
                } else if(startDate.compareTo(endDate) == 0) {
                    d.add(endDate);
                    return d;
                }
            }
        }
    }

    public static void main(String[] args) {
        new Days();
    }
}

Answer 7

I'm not sure if this is the most performant solution, but you could simply create a range of dates, check for frequency, and return that with the highest frequency:

public static Date getMaxOccurence(Booking[] booking) {
    List<Date> dates = new ArrayList<Date>();
    Date max = new Date();
    int freq = 0;
    for (Booking b : booking) {
        Calendar calendar = new GregorianCalendar();
        calendar.setTime(b.getStartDate());

        while (calendar.getTime().before(b.getEndDate())) {
            Date result = calendar.getTime();
            dates.add(result);
            int curr = Collections.frequency(dates, result);
            if (curr > freq) {
                freq = curr;
                max = result;
            }
            calendar.add(Calendar.DATE, 1);
        }
    }
    return max;
}

ideone demo