search for interval overlap in list of intervals?

by

For completeness’ sake, I’d like to add that there is a well-known data structure for just this sort of problem, known (surprise, surprise) as an interval tree. It’s basically an augmented balanced tree (red-black, AVL, your pick) that stores intervals sorted by their left (low) endpoint. The augmentation is that each node stores the largest right (high) endpoint in its subtree. This tree allows you to find all overlapping intervals in O(log n) time.

It’s described in CLRS 14.3.

More Related Contents:

  1. Calculate the sum with minimum usage of numbers
  2. Sum a number with divisors to get another number
  3. Priority scoring algorithm [closed]
  4. What is the optimal algorithm for the game 2048?
  5. How to count the number of set bits in a 32-bit integer?
  6. Algorithm to return all combinations of k elements from n
  7. Reverse the ordering of words in a string
  8. Converting a Uniform Distribution to a Normal Distribution
  9. Can hash tables really be O(1)?
  10. Graph Algorithm To Find All Connections Between Two Arbitrary Vertices
  11. What is Sliding Window Algorithm? Examples?
  12. Choosing n numbers with fixed sum
  13. Fast way to calculate n! mod m where m is prime?
  14. Sum-subset with a fixed subset size
  15. What is a good Hash Function?
  16. Binary Search in Array
  17. Algorithm to tell if two arrays have identical members
  18. Quicksort vs heapsort
  19. What is the most efficient algorithm to find a straight line that goes through most points?
  20. Find 2 numbers in an unsorted array equal to a given sum
  21. Closest point to a given point
  22. What is amortized analysis of algorithms? [closed]
  23. Find cycle of shortest length in a directed graph with positive weights
  24. How modern X86 processors actually compute multiplications?
  25. Random points inside a parallelogram
  26. How is 2D bin packing achieved programmatically?
  27. need an algorithm for collapsing netblock ranges into lists of superset ranges
  28. Why use binary search if there’s ternary search?
  29. Algorithm for reflecting a point across a line
  30. What is the most efficient way to encode an arbitrary GUID into readable ASCII (33-127)?

Leave a Comment