Aveiro_quanyue's blog

By Aveiro_quanyue, history, 12 months ago, In English

We have $$$n$$$ closed intervals. Find a set of intervals with maximum cardinality such that the intervals in this set intersect pairwise.

As far as I know, we can use the famous greedy algorithm to solve the maximum interval independent set problem, i.e., the interval scheduling problem. But how about the maximum interval clique problem? We can convert it into an interval graph which is also chordal, and find the maximum clique using LexBFS in $$$O(n^2)$$$ time as the number of edges in the interval graph is $$$O(n^2)$$$. What about an $$$O(nlog^kn)$$$ algorithm? Am I overthinking?

  • Vote: I like it
  • 0
  • Vote: I do not like it

»
12 months ago, # |
  Vote: I like it +3 Vote: I do not like it

Yes, you are overthinking. For every two intervals to intersect, all of them must intersect. Hence, you can just fix a point, count the intervals containing that point and take the maximum value obtained this way. So (up to normalization), you get Nlog (or even linear if you assume them to be normalized).