Possible Interview Question: How to Find All Overlapping Intervals
algorithm
Solution
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.
Problem
It's not an interview question per se, as I came across this in my project, but I figured it could be a decent intervew question. You have N pairs of intervals, say integers. You're required to indentify all intervals that overlap with each other in O(N) time. For example, if you have {1, 3} {12, 14} {2, 4} {13, 15} {5, 10} the answer is {1, 3}, {12, 14}, {2, 4}, {13, 15}. Note that you don't need to group them, so the result can be in any order like in the example. I just threw in O(N) time because the KMP algorithm takes O(N) for string search. :D The best I came up with and what I'm using right now in the project is O(N^2). Yeah, brute force is pretty sad, but no one complains so I won't refactor it. :P Still, I was curious if a greater mind has a more elegant solution.