Given a set of intervals, find the interval which has the maximum number of intersections

by

Don’t use an interval tree. Create an event for each interval endpoint, so that each interval has a start event and a stop event. Process these events in order. (Order starts before stops if a measure-zero intersection counts as an intersection, or stops before starts otherwise.)

Initialize a map C from intervals to numbers. Initialize the start count s = 0 and the stop count t = 0. To process a start event for interval i, set s = s + 1 and then C(i) = -(t + 1). To process a stop event for interval i, set t = t + 1 and then C(i) = C(i) + s.

At the end, C maps intervals to their intersection counts. This algorithm is O(n log n) because of the sorting; that running time is optimal if the endpoints can be added and compared only, by fairly standard computational geometry techniques.

More Related Contents:

  1. How to create the most compact mapping n → isprime(n) up to a limit N?
  2. Reverse the ordering of words in a string
  3. How to create the most compact mapping n → isprime(n) up to a limit N?
  4. Hash table runtime complexity (insert, search and delete)
  5. How to implement a queue using two stacks?
  6. How do you validate a binary search tree?
  7. design a stack such that getMinimum( ) should be O(1)
  8. Best algorithm to test if a linked list has a cycle
  9. How to delete in a heap data structure?
  10. Array remove duplicate elements
  11. What is the difference between tree depth and height?
  12. How Do I Choose Between a Hash Table and a Trie (Prefix Tree)?
  13. What is the fastest way to find the closest point to a given point?
  14. insert, delete, max in O(1)
  15. In Order Successor in Binary Search Tree
  16. Skip List vs. Binary Search Tree
  17. Algorithm for autocomplete?
  18. graph – Dijkstra for The Single-Source Longest Path
  19. What is the advantage to using Bloom filters?
  20. Why does Dijkstra’s algorithm use decrease-key?
  21. How can I return an array of struct in solidity?
  22. Search a sorted 2D matrix [duplicate]
  23. The intersection of all combinations of n sets
  24. Why increase pointer by two while finding loop in linked list, why not 3,4,5?
  25. Why are hash table expansions usually done by doubling the size?
  26. Algorithm for merging two max heaps?
  27. What are probabilistic data structures?
  28. How to find the number of different shortest paths between two vertices, in directed graph and with linear-time?
  29. Why is vector array doubled?
  30. How to apply binary search O(log n) on a sorted linked list?

Leave a Comment