# Tag Info

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 ...
• 16.7k

### 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 ...
• 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 ...
• 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 ...
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 ...
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 ...

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