0
$\begingroup$

Given a set of intervals on the real line, compute the largest subset of pairwise intersecting intervals (an interval in the subset must intersect with every other interval in the subset). Design a greedy algorithm that computes an optimal solution.

| cite | improve this question | | | | |
$\endgroup$
  • $\begingroup$ Can you add a reference to the original problem where a greedy algorithm is wanted? $\endgroup$ – John L. Aug 4 '19 at 13:22
  • 1
    $\begingroup$ What did you try? Where did you get stuck? We're happy to help you understand the concepts but just solving homework-style exercises (your post is an order, not a question) is unlikely to really do that. $\endgroup$ – David Richerby Aug 7 '19 at 12:15
1
$\begingroup$

First, suppose the intervals $[l_1,r_1],\ldots,[l_n,r_n]$ are pairwise intersecting, then we have $l_i\le r_j$ for any $i,j$, which means for any $i$, $l_i\le\max_k l_k\le r_k$, i.e. all these intervals contain the point $\max_k l_k$.

The observation above leads to the algorithm mentioned in jaxa 9831's answer:

First, sort the intervals according to their left endpoints. Then at each left endpoint, check how many intervals cross that point. Finally, report the optimal one.

To efficiently find the point that maximum intervals cross, we can use an algorithm mentioned in GeeksforGeeks. Roughly speaking, we first sort all endpoints, and maintain a counter initialized with 0. We then travel these endpoints from left to right. Each time we come across a left endpoint, we increase the counter by 1, while each time we come across a right endpoint, we decrease the counter by 1. The maximum value of the counter represents the maximum number of pairwise intersecting intervals.

| cite | improve this answer | | | | |
$\endgroup$
0
$\begingroup$

First, sort the intervals according to their left endpoints. Then at each left endpoint, check how many intervals cross that point. Finally, report the optimal one. Time complexity - $\mathcal {O}(n^2)$

| cite | improve this answer | | | | |
$\endgroup$
  • 1
    $\begingroup$ "Check how many interval crosses that point." You might want to explain how to do that efficiently. The naive approach will lead to $\mathcal \Theta(n^2)$ worst-time complexity. $\endgroup$ – John L. Jul 31 '19 at 6:39
  • $\begingroup$ Yes, please explain how to do this efficiently. "Check how many intervals crosses that point." $\endgroup$ – Tejas Oberoi Jul 31 '19 at 17:03
  • $\begingroup$ Let $t$ be an endpoint, an interval $[a,b]$ crosses this endpoint iff $a \leq t \leq b$. By this way, we can check at each endpoint. The total number of endpoints is 2$n$. Hence time complexity is $\mathcal{O}(n^2)$ $\endgroup$ – jaxa 9831 Aug 1 '19 at 4:19

Not the answer you're looking for? Browse other questions tagged or ask your own question.