Merging a List of Time-Range Tuples That Have Overlapping Time-Ranges

Collapse a list of range tuples into the overlapping ranges

import operator
lst = [(0, 2), (1, 2), (0, 4), (2,6), (23, 2), (22, 6), (26, 2), (26, 2), (26, 2)]
lst.sort(key=operator.itemgetter(1))
for i in reversed(xrange(len(lst)-1)):
    start, length = lst[i]
    for j in xrange(i+1, len(lst)):
        lstart, llength = lst[j]
        if start >= lstart and start + length <= lstart + llength:
            del lst[i]
            break
print lst
#[(0, 4), (2, 6), (22, 6)]

How can I merge multiple overlapping date ranges and create new ones?

Here's a sketch of an algorithm to do this:

The data struct would be:

type Boundary struct {
   Time time.Time
   AddRemove int
   Value int
}

A Boundary would represent a Value added or removed from the list of values at a given time. For a range:

[from,to]=number

you create two Boundary objects:

b1:=Boundary{Time:from,AddRemove: 1, Value: number}
b2:=Boundary{Time:to,AddRemove:-1,Value:number}

You can then sort all boundary objects by time and AddRemove. If times are equal, you should process adds first, then removes. Once this is done, you can process the boundary objects, and create your ranges:

last:=time.Time{}
values:=map[int]struct{}{}
for _,b:=range boundaries {
   if last.IsZero() {
      last=b.Time
      values[b.Value]=struct{}{}
   } else {
      // Create a new range here with [last,b.Time] with values given in `values`
      if b.AddRemove==1 {
        values[b.Value]=struct{}{}
      } else {
        delete(values,b.Value)
      }
      last=b.Time
   }
}

How can I append overlapping tuples in Python and list them in order?

Assuming your meeting times will not overlap each other because you cannot be in two places in the same time. Thus, (1,4) (3,5) cannot happen.

One way to do this is to iterate with a variable that remembers the previous tuple, in this case I'll name it "previous", I'll keep your variable "m" as it is.

Every time you go on the next tuple in your meeting times, you compare the ending meeting time from previous tuple with current starting meeting time. Then you remove the previous tuple because it will be a duplicate. If no condense operation, then you can just append to the list and then set "m" to "previous" for the next iteration.

# Variable containing list of tuples
meeting_times = [(0, 1), (3, 5), (4, 8), (10, 12), (9, 10)]

# Sort meetings by start time
ordered_list = sorted(meeting_times)

print('Given time tuple: ', ordered_list)

def condensed_meeting_time(append_meeting_time, previous):
    # For each number in the variable
    for m in ordered_list:
        if previous: # This is to catch empty tuple that was initial
            if m[0] == previous[1]: # If current starting meeting time is equal to previous ending meeting time ...
                del append_meeting_time[-1] # Remove the previous element
                append_meeting_time.append( (previous[0], m[1]) ) # Create new tuple to merge previous start time to current ending time
            else: # If the time does not overlap, append normally and set current meeting time to 'previous' for next iteration
                append_meeting_time.append(m)
                previous = m
        else: # Base case to append the first element.
            append_meeting_time.append(m)
            previous = m
    return append_meeting_time

print('After condensed range: ',condensed_meeting_time([], ()))

This is the output I've got:

Given time tuple:  [(0, 1), (3, 5), (4, 8), (9, 10), (10, 12)]
After condensed range:  [(0, 1), (3, 5), (4, 8), (9, 12)]

I hope this helps.

Combine overlapping ranges of numbers

If I understand you correctly, you can do this:

from itertools import combinations
l = [[83,77],[103,97],[82,76],[101,95],[78,72],[97,91],[72,66],[89,83],[63,57],[78,72],[53,47],[65,59],[41,35],[50,44],[28,22],[34,28],[14,8],[16,10]]

def any_items_overlap(l):

    # For each possible pair of lists in l
    for item1, item2 in combinations(l, 2):

        max1, min1 = item1
        max2, min2 = item2

        if min1 > max2 or max1 < min2:
            # no overlap so ignore this pair
            continue

        else:  # One of the combinations overlaps, so return them
            return item1, item2

    return None

while True:

    if not any_items_overlap(l):
        # No items overlapped - break the loop and finish
        print(l)
        break

    else:  # There are still overlaps
        item1, item2 = any_items_overlap(l)

        # Remove the items from the main list
        l.remove(item1)
        l.remove(item2)

        # Replace them with a merged version
        item_values = item1 + item2
        l.append([max(item_values), min(item_values)])
        # Start the loop again to check for any other overlaps

This gives:

[[41, 35], [103, 91], [65, 57], [53, 44], [34, 22], [16, 8], [89, 66]]

Related Topics