Merging a list of time-range tuples that have overlapping time-ranges
algorithm, merge, python
Solution
A few ways to make it more efficient, Pythonic:
- Eliminate the `set()` construction, since the algorithm should prune out duplicates during in the main loop.
- If you just need to iterate over the results, use `yield` to generate the values.
- Reduce construction of intermediate objects, for example: move the `tuple()` call to the point where the final values are produced, saving you from having to construct and throw away extra tuples, and reuse a list `saved` for storing the current time range for comparison.
Code:
def merge(times):
saved = list(times[0])
for st, en in sorted([sorted(t) for t in times]):
if st <= saved[1]:
saved[1] = max(saved[1], en)
else:
yield tuple(saved)
saved[0] = st
saved[1] = en
yield tuple(saved)
data = [
[(1, 5), (2, 4), (3, 6)],
[(1, 3), (2, 4), (5, 8)]
]
for times in data:
print list(merge(times))
Problem
I have a list of tuples where each tuple is a `(start-time, end-time)`. I am trying to merge all overlapping time ranges and return a list of distinct time ranges. For example ``` [(1, 5), (2, 4), (3, 6)] ---> [(1,6)] [(1, 3), (2, 4), (5, 8)] ---> [(1, 4), (5,8)] ``` Here is how I implemented it. ``` # Algorithm # initialranges: [(a,b), (c,d), (e,f), ...] # First we sort each tuple then whole list. # This will ensure that a<b, c<d, e<f ... and a < c < e ... # BUT the order of b, d, f ... is still random # Now we have only 3 possibilities #================================================ # b<c<d: a-------b Ans: [(a,b),(c,d)] # c---d # c<=b<d: a-------b Ans: [(a,d)] # c---d # c<d<b: a-------b Ans: [(a,b)] # c---d #================================================ def mergeoverlapping(initialranges): i = sorted(set([tuple(sorted(x)) for x in initialranges])) # initialize final ranges to [(a,b)] f = [i[0]] for c, d in i[1:]: a, b = f[-1] if c<=b<d: f[-1] = a, d elif b<c<d: f.append((c,d)) else: # else case included for clarity. Since # we already sorted the tuples and the list # only remaining possibility is c<d<b # in which case we can silently pass pass return f ``` I am trying to figure out if - Is the a an built-in function in some python module that can do this more efficiently? or - Is there a more pythonic way of accomplishing the same goal? Your help is appreciated. Thanks!