3
$\begingroup$

The problem involves date intervals filtered by days of week. For example, the filtered interval {2001 APR 1 - 2001 APR 30, 17} corresponds to all Mondays and Sundays between April 1 and April 30. Here is the problem: given a collection of filtered date intervals, find a minimal collection of such intervals that cover exactly the same set of dates.

Initially, I naively assumed that this can be solved by sorting the intervals by start dates and merging consecutive intervals, if possible. Here is a counterexample to this approach. Consider the date interval given by the pattern $56712345671234$, where each number stands for a day of week. Assign zero-based indices to the dates in this pattern. The set of dates covered by intervals $\{0-2, 567\}$, $\{3-9, 1234\}$, $\{10-13, 12\}$ can be covered by the collection $\{0-6, 1234567\}, \{7-13, 12\}$. The merging algorithm will fail to merge any intervals and will output three intervals as the minimal cover instead of two.

Is there a well-known algorithm for this problem? Can it be solved in $O(n \log n)$ where $n$ is the number of input intervals?

$\endgroup$
  • $\begingroup$ Without the holes this can be solved in time $O(n\log n)$ using a greedy algorithm that always chooses the interval with the earliest starting point, breaking takes by taking the longest possible interval. $\endgroup$ – Yuval Filmus Apr 11 '18 at 11:20
2
$\begingroup$

This can be solved in $O(n \log n)$ time by a greedy algorithm. Take the earliest week you need to cover (that isn't covered yet). Pick the set of days-of-the-week that you need to cover in that week. Choose a filtered data interval that starts with that week, uses that mask, and extends as far as possible. Add that to your collection, and repeat.

I'll let you work out the proof that it is correct, via an exchange argument. How to prove greedy algorithm is correct may be helpful.

To make this run efficiently with a $O(n \log n)$ worst-case time, you'll need a proper data structure for storing the filtered intervals and figuring out how far you can extend an interval. I'll let you figure that out, but a hint: a balanced binary search tree provides $O(\log n)$ running time for all basic operations.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ Can you elaborate on how to extend the interval as far as possible in an efficient manner? $\endgroup$ – Narek Margaryan Apr 12 '18 at 14:09
  • $\begingroup$ @user1978522, see edit. This is your exercise so I'm going to let you work out the details. If you just want to build it in practice, as long as the filtered intervals aren't too long, almost any data structure will be fine (e.g., a hashtable). If you care about worst-case inputs or the theoretical running time analysis, use a balanced binary search tree. $\endgroup$ – D.W. Apr 12 '18 at 15:22

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.