Deciding whether open real intervals are pairwise disjoint has comparison complexity . Sort by left endpoint and scan the maximum previous right endpoint for the upper bound. For the lower bound, map integer keys to . Such intervals intersect exactly when the original integers agree. Each comparison between endpoints and , with , is determined by a comparison of and their fixed offsets, so the reduction preserves the comparison model. Apply the element distinctness problem lower bound.
Articles by others on the same topic
There are currently no matching articles.