Possible Interview Question: How to Find All Overlapping Intervals

by

Throw the endpoints of the intervals into an array, marking them as either start- or end-points. Sort them by breaking ties by placing end-points before start-points if the intervals are closed, or the other way around if they’re half-open.

1S, 2S, 3E, 4E, 5S, 10E, 12S, 13S, 14E, 15E

Then iterate through the list, keeping track of how many intervals we’re in (this equates to number of start-points processed minus number of end-points). Whenever we hit a start-point while we are already in an interval, this means we must have overlapping intervals.

1S, 2S, 3E, 4E, 5S, 10E, 12S, 13S, 14E, 15E
    ^                          ^
   overlap                    overlap

We can find which intervals overlap with which by storing data alongside the end-points, and keeping track of which intervals we’re in.

This is an O(N logN) solution, with sorting being the main factor.

More Related Contents:

  1. Complexity of absolute difference and sum
  2. C++ Sorting Algorithms [closed]
  3. What is tail recursion?
  4. Algorithm for finding the fewest rectangles to cover a set of rectangles without overlapping
  5. Getting the closest string match
  6. How to compute Discrete Fourier Transform?
  7. Difference between Big-O and Little-O Notation
  8. Efficient list intersection algorithm
  9. Rounding to an arbitrary number of significant digits
  10. Store the largest 5000 numbers from a stream of numbers
  11. What is Constant Amortized Time?
  12. How can I compute a Cartesian product iteratively?
  13. Puzzle: Find largest rectangle (maximal rectangle problem)
  14. How can I calculate the age of a person in year, month, days?
  15. Performing Breadth First Search recursively
  16. Quicksort: Iterative or Recursive
  17. Polygon enclosing a set of points
  18. Find the index of a given permutation in the sorted list of the permutations of a given string
  19. Algorithm to mix sound
  20. finding a^b^c^… mod m
  21. Sorting a sequence by swapping adjacent elements using minimum swaps
  22. Retrieving the top 100 numbers from one hundred million of numbers [duplicate]
  23. What is password hashing? [closed]
  24. Can an array be grouped more efficiently than sorted?
  25. Algorithm to find all Latitude Longitude locations within a certain distance from a given Lat Lng location
  26. Compute the area of intersection between a circle and a triangle?
  27. Unbiased random number generator using a biased one
  28. maximum subarray of an array with integers [duplicate]
  29. Quadratic algorithm for 4-SUM
  30. CUDA stream compaction algorithm

Leave a Comment