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.

$\endgroup$

closed as unclear what you're asking by Evil, Juho, dkaeae, David Richerby, vonbrand Aug 7 at 14:42

Please clarify your specific problem or add additional details to highlight exactly what you need. As it's currently written, it’s hard to tell exactly what you're asking. See the How to Ask page for help clarifying this question. If this question can be reworded to fit the rules in the help center, please edit the question.

  • $\begingroup$ Can you add a reference to the original problem where a greedy algorithm is wanted? $\endgroup$ – Apass.Jack Aug 4 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 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.

$\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)$

$\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$ – Apass.Jack Jul 31 at 6:39
  • $\begingroup$ Yes, please explain how to do this efficiently. "Check how many intervals crosses that point." $\endgroup$ – Tejas Oberoi Jul 31 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 at 4:19

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