CODEWITHSUNDEEP
pythonintervalsoverlapping
Asmita Poddar
Asmita Poddar

Reputation: 532

Remove Overlapping Intervals & Divide into Non-overlapping Intervals Python

I have a sorted list of intervals List1: [1,10], [2,4], [6,8], [20,30], [24,28], [35,40], [45,50]

where I know that the overlapping intervals are List2: [2,4], [6,8], [24,28]

from which I want to get the non-overlapping intervals, such that the Output is: [1,2], [4,6], [8,10], [20,24], [28,30], [35,40], [45,50]

How can I do this efficiently in Python?

My first thought is that I should create a new list List1 of divided intervals for every overlapping interval I come across in List2, and delete the corresponding element of List2 (continue this until List2 is empty), but I've been having some trouble getting this to work. This seems different in nature than many interval problems, so any suggestion would be great!

Upvotes: 0

Views: 714

Answers (1)

Gabio
Gabio

Reputation: 9494

I don't know if it's the most efficient way but it might be a good starting point for you:

data = [[1, 10], [2, 4], [6, 8], [20, 30], [24, 28], [35, 40], [45, 50]]
flat_data = sorted([x for sublist in data for x in sublist])
new_intevals = [flat_data[i:i + 2] for i in range(0, len(flat_data), 2)]

print(new_intevals)
# output: [[1, 2], [4, 6], [8, 10], [20, 24], [28, 30], [35, 40], [45, 50]]

Upvotes: 1

Related Questions