TIFR CSE 2023 | Part B | Question: 3

Question

Given a set $\mathcal{F}$ of intervals $\left(s_{i}, t_{i}\right)_{i=1}^{n}$ on the integer line (assume all $s_{i}, t_{i}$ are distinct), a subset $S$ of $\mathcal{F}$ is said to be independent if no two intervals in $S$ have a non-empty intersection.

Consider greedy algorithms of the following type:

Here are three possible choices for the ordering $\sigma$ :

$\text{(C1)}$ $\sigma$ arranges the intervals in $\mathcal{F}$ in increasing order of $s_{i}$.
$\text{(C2)}$ $\sigma$ arranges the intervals in $\mathcal{F}$ in increasing order of $t_{i}$.
$\text{(C3)}$ $\sigma$ arranges the intervals in $\mathcal{F}$ in increasing order of $\left|s_{i}-t_{i}\right|$.

For which of these choices of the ordering $\sigma$ does the algorithm always produce an independent set of $\mathcal{F}$ of maximum size?

• A. Choice $\text{(C1)}$ only
• B. Choice $\text{(C2)}$ only
• C. Choice $\text{(C3)}$ only
• D. Choices $\text{(C2)}$ and $\text{(C3)}$, but not choice $\text{(C1)}$
• E. Choices $\text{(C1)}$ and $\text{(C2)},$ but not choice $\text{(C3)}$

Answer 1

At first we have to understand what the question asks.

 

Here $F$ is the set of $(s_i, t_i)$ pairs which represents an interval in number line, starts frm $s_i$ and ends at $t_i$.

A set of intervals $S$ are independent if no two intervals in $S$ have a non-empty intersection, that is all pairs of intervals in $S$ have empty intersection.

 

For example,
$S = \{ (2,4), (3,5)\}$ is not independent.
$S = \{ (2,4), (4,5), (6,8)\}$ is independent.

 

This is similar to the job Job Scheduling with maximum profit problem, where all the jobs have the same profit. So we have to maximize number of jobs to maxmize our profits.

A Intuitive approach:

This is the easiest approach, that is to come uip with small counter examples for each one of them:

$F = \{ (1,8), (2,5), (4,6), (5, 8)\}$
Using $\sigma_1$, $S = \{(1,8)\}$
Using $\sigma_2$, $S = \{(2,5), (5,8)\}$
Using $\sigma_3$, $S = \{(4,6)\}$
Our objective is to maximize $|S|$, so $\sigma_2$ approach is the only one producing largest independent set.
So from this single example, we have counter example for choices C1 and C3. So definitely they won't always produce an independent set of the largest size.

Now from the options, we can see the only option satisfying our conclusion is (B).

 

From counter examples, we cannot prove that ordering $\sigma$ according to one the choices, the algorithm always produce an independent set of maximum size. We can only only prove the negation of the statement by using examples.