Skip to main content
5 votes
Accepted

Minimum number of intervals from a set to cover all intervals of another set

Of all intervals you need to cover, focus now on the one that ends earliest. This interval has to be covered, so take a covering interval that covers this interval, and that ends the latest. Pick that ...
Pål GD's user avatar
  • 16.7k
2 votes

Detect if an interval is fully covered by union of previous intervals in sequence

The intersection of a sequence of intervals $I_1, ..., I_p$ is $$\left[ \max_{i \leq p} s(I_i), \min_{i \leq p} f(I_i) \right],$$ where $s$ and $f$ are the start and finish times is an interval. From ...
Pål GD's user avatar
  • 16.7k
1 vote

Detect if an interval is fully covered by union of previous intervals in sequence

I think I have worked out a solution that takes $O(n \log n)$ time. It relies on a regular interval tree which has $O(\log n + m)$ query (for $m$ overlapping intervals) and $O(\log n)$ insertion and ...
MattDs17's user avatar
  • 163
1 vote
Accepted

Turning stacked overlapping intervals (with associated data) into non-overlapping intervals

I found an answer that works well. The basic concept is to iterate a sorted list of all 'points of interest' (start and end location of intervals). Iterating that (scan line) allows us to maintain a ...
Johannes Weiss's user avatar
1 vote

Is minimum interval hitting problem NP-HARD?

It should be solvable in Polynomial time (in the number of constraints + $\max j$) by MaxFlow algorithms. Consider first this link explaining how you can determine the minimum amount of flow on a ...
Bernardo Subercaseaux's user avatar
1 vote

Proving the correctness of a greedy algorithm for the Circular Scheduling Problem

Your algorithm is not correct. Consider intervals [1,7], [8, 14], [15, 21], [22,28], [13,16], [2,9], [3,10], [4,11], [17,23], [18,24], [19, 25]. Your algorithm chooses [13,16] first, as it only ...
Bernardo Subercaseaux's user avatar

Only top scored, non community-wiki answers of a minimum length are eligible