I’m trying to maximize attendance to a event given a list of busy times for each person. The event can be scheduled anytime between a certain date and hours (Ex. March 1st to March 8th from 9-5) and that attendance is maximized.
So far I’ve tried using a sliding window approach, and a counting approach described here (https://www.geeksforgeeks.org/find-the-point-where-maximum-intervals-overlap/) however I only managed to get the sliding window approach working with a time complexity of O(n^3) which unfortunately is not good enough for my use case. The counting approach does not work because I can find the maximum interval but not for a certain timeframe.
A worst case scenario use case would be ~500 people and a month timespan.
Any help would be much appreciated.
Advertisement
Answer
Solved using a Interval Tree (https://en.wikipedia.org/wiki/Interval_tree)