1
$\begingroup$

Here is a modification of the weighted interval scheduling problem.

Given $n$ intervals by their end points $s_i$ and $t_i$ for $1 ≤ i ≤ n$, I want to minimize number of intervals so that every interval has a nonempty intersection with one of the selected intervals. In other words, select $S ⊆ {1,..., n}$ such that for each $1 ≤ j ≤ n$, interval $j$ intersects with some interval $i ∈ S$. We say that the $j^{th}$ interval $[s_j, t_j]$ overlaps with $i^{th}$ interval $[s_i, t_i]$ if there exists a point $x$ such that $x$ belongs to the $i^{th}$ interval and the $j^{th}$ interval. A point $x$ belongs to an interval $[s, t]$ if $s ≤ x ≤ t$. Assume that $s_i ’s$ and $t_i's$ are distinct.

What I'm confused on is what this problem is even asking. It says minimize the number of intervals so that every interval has a non-empty intersection with a selected interval. So I get that means I want to find an interval that overlaps with another interval. But am I trying to find a sequence that avoids this as much as possible? In other words, am I just trying to set it up so that I maximize number of intervals while also minimizing overlapping intervals or am I trying to do something different?

$\endgroup$
3
  • $\begingroup$ "interval $j$ intersects with some interval $i\in S$" Do you mean "the $j^{th}$ interval intersects with some $i^{th}$ interval where $i\in S$? $\endgroup$
    – John L.
    Commented Oct 25, 2018 at 5:16
  • $\begingroup$ By the way, I am confused by the tone of your problem. "I want to minimize number of intervals ..." That implies you are the author of the modification. Then how can you not know your goal? If this modification comes from elsewhere, such as an online course or contest, a textbook or a paper, can you add a url or reference to the question? $\endgroup$
    – John L.
    Commented Oct 25, 2018 at 5:20
  • $\begingroup$ Yes, I mean the j-th interval intersects the i-th interval at some i in S. And, assume "I" is equal to "You." This is exactly as the problem stated. Unfortunately, I don't have an online link. @Apass.Jack $\endgroup$
    – user40759
    Commented Oct 25, 2018 at 5:23

1 Answer 1

0
$\begingroup$

Let us check some simple examples.

Suppose there are three intervals [1,3], [2,5], [4, 6]. Then the wanted number is 1. Here is how. Let $T$ be any two of the intervals. Then every interval will has a nonempty intersection with one of the intervals in $T$. For example, you can let $T$ be {[1,3], [2,5]}. You can also let $T$ be {[1,3], [4,6]}. On the other hand, Let $M$ be the set of [2,5], i.e., $M$={[2,5]}. Then every interval will has a nonempty intersection with the only one interval in $M$, [2,5]. Since the wanted number can not be smaller than 1, it is 1.

For a slightly more interesting example, suppose there are 5 intervals [1, 3], [2,5], [4, 7], [6,9], [8,10], where each interval intersects its two neighboring intervals.

  • The wanted number is 2. Why? Firstly, any interval will not intersect either [1,3] or [8,10]. So one interval is not enough. Secondly, consider intervals [2,5] and [8,10]. We can see that every interval will intersect one of [2,5] and [8,10]. So two intervals are enough.
  • If you name those five intervals A, B, C, D, E respectively and connect a pair of letters if the corresponding two intervals intersects, you get a graph with vertices {A,B,C,D,E} with edges AB, BC, CD, DE. (Graphs obtained this way are called interval graphs.) Now it is easy to translate our problem about intersecting intervals into a problem about graphs. The new problem is called the minimum dominating set of a graph.

Here is an equivalent version of the problem that is much simpler.

Given $n$ fixed intervals all of whose endpoints are distinct. Select some intervals such that the intersection of every original interval and the union of selected intervals is nonempty. How to minimize the number of intervals selected?

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.