Given a list of date ranges, find the date that has the maximum time

Question

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

 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 all 4 times.

The solution that comes to my mind:

• repeat all dates from minimum startDate to maximum endDate in the list
• save the amount of all orders for all dates.
• finally return the date with the maximum quantity.

But this is not an effective solution. How can I find a busy day efficiently?

Answer 1

• for simplicity, give each date its own index (for example, date min has index 0, next day 1, etc.) and initialize an array filled with zeros
• iterating over all ranges for an element with an index step of the start date in the array, and decrement by the end date. (for example, if any date d occurs 3 times at the beginning of the range and 5 times as the end of the range, there should be -2)
• now, iterating over all dates from the beginning of the array and adding the current element to your counter (basically, the value of the counter on date d , how often is it inside ranges)
• Answer - maximum counter value

The algorithm works O (n) , where n is the number of days between minDate and maxDate

PS. The solution mentioned by Patrick Parker in this post also works, but it takes O (m * log (m)) time, where m is the number of ranges. Therefore, you must choose a solution depending on the specification of the task.

Answer 2

Well, it's pretty ugly, but we can do it with 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 reservation get all 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 calculate how many times each date appears in a new stream.

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

and finally, find the maxim - the most common date:

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

In this case, the result will be optional [2016-10-13 = 4];

Answer 3

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

You can convert the date to a number by simply adding the values ​​of the year, month, and day, for example:

 2016-10-12 -> 20161012 

Then you can follow this method . Here is what I did, without the parts of converting 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 4

I would like to point out a property that can set you in the right direction.

The most frequent day will either be the end point (start or end date), or they will be associated with the end point.

So, if it’s enough to find one day from the tied days, you only need to consider the days that reach the endpoint.

Now, how will you reliably increase the frequency for each endpoint? Processing is ok. But this is not enough to start the start and end in the order of start. start and end must be counted in date order.

Answer 5

For each entry {startDate, endDate} create two tuples {startDate,'start'} , {endDate, 'end'} . First, sort them by date, and the second by the second, making sure that end comes after start . (As far as I understand, the intervals are inclusive, so you do not want to discard the final reservation before taking into account what begins on the day when the previous one ends).

Then go through the tuples in the order described above, increasing the counter with each start , decreasing with each end and tracking the maximum so far. The maximum booking period.

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

Answer 6

I'm not sure if this is the most efficient solution, but you can just create a series of dates, check the frequency and return them with the maximum 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

Answer 7

Although this may not be the most efficient way to do this, if you are not working with millions of dates, it will be pretty fast. I added several thousand dates in the example below, and it did not take much time 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(); } }