Skip to main content

New answers tagged

0 votes

Cover a set of points using subintervals of a list of intervals

There might exist a polynomial time algorithm for this. Here are some pointers: Suppose the set of points sorted in ascending order. The intervals are also sorted in ascending order by their start ...
codeR's user avatar
  • 1,455
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
0 votes

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

Note, that $$I_i \subseteq \bigcup_{k < i} I_k \iff I_i \cap \overline{\bigcup_{k < i} I_k} = \emptyset \iff \Big(\big((I_i \setminus I_1) \setminus I_2\big) ... \setminus I_{i - 1}\Big) = \...
Knogger's user avatar
  • 1,302
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

Top 50 recent answers are included