28/01/2018

[Java] Find maximum number of concurrent events in a calendar

This problem can be generalized to: find the maximum number of overlapping entries in a time series. We will focus on a calendar example where each event has a start and end time; you can find here the implementation of the CalendarEntry and CalendarEvent classes.

This problem is very similar to the one about verifying if all open parentheses in an expression have a matching closing parenthesis. In both cases we need to be able to find start and end points of an interval and verify where do they reside.

But the calendar entries might not be given in a sorted order already so to solve our problem we need to first split them in bot start and end points, then sort the points by comparing the times and breaking ties by giving precedence to the start points - this is very important! - if precedence is given to the end points we are not tracking the information we need, therefore double check that compareTo override :)

After the input data is sorted, we simply need to walk through the sorted list/array/whatever and keep a counter that we increase every time we encounter a start point and decrease when an end point is found. The maximum value of the counter is also the maximum number of concurrent events in the calendar.

You can check the implementation of getMaxCalendarOverlap on my Gist alongside some test cases in CalendarJTests.

No comments:

Post a Comment

With great power comes great responsibility.

Da grandi poteri derivano grandi responsabilità.