I'm working with a list of tuples in Python, where each tuple contains two integers representing the start and end points of intervals. I'm trying to figure out a way to efficiently identify non-overlapping intervals from this list. My current method, which involves nested loops to compare each interval with every other interval, isn't efficient, especially when the list is large.
Can anyone point me in the direction of relevant algorithms or libraries that can help me with this? :) Thank you!
Sort the start & end points of every interval, where each endpoint is associated with an interval id (say the index of the interval in a list, or whatever makes sense for how they're stored).
Now parse your sorted array of points, maintaining a set of currently active points, initially empty. As you encounter a start point, add the associated interval to your set, and associate it with everything else already in the set. When you encounter an end point, remove that from the set.
Once done, all overlapping intervals are in associated pairs, so the unassociated pairs are your nonoverlapping intervals.
E.g.
0 [1,5]
1 [3,7]
2 [6,9]
sorted array of points associated with intevals: [1=>0, 3=>1, 5=>0, 6=>2, 7=>1, 9=>2]
parse point 1: set = {0}, pairs = {}
parse point 3: set = {0,1}, pairs = {(0,1}}
parse point 5: set = {1}, pairs = {(0,1)}
parse point 6: set = {1,2}, pairs = {(0,1), (1,2)}
parse point 7: set = {2}, pairs = {(0,1), (1,2)}
parse point 9: set = {}, pairs = {(0,1), (1,2)}
We have that intervals 0 & 1 overlap, as do 1 & 2, so our only non-overlap is 0 & 2.
