timeline.py

import heapq


log = [
    {'event-name': 'A', 'event-start': 0,  'event-finish': 10},
    {'event-name': 'B', 'event-start': 5,  'event-finish': 20},
    {'event-name': 'C', 'event-start': 10, 'event-finish': 30},
    {'event-name': 'D', 'event-start': 30, 'event-finish': 50},
    {'event-name': 'E', 'event-start': 30, 'event-finish': 35},
    {'event-name': 'F', 'event-start': 30, 'event-finish': 40},
]


# In case a event starts at the same time as another finishes, we make
# sure that we first free the lane so it can be reassigned.
EVENT_FINISH, EVENT_START = 0, 1


# Create start events for each log entry, sorted by the event start
# timestamp and type.
events = []
for l in log:
    heapq.heappush(
        events,
        (l['event-start'], EVENT_START, l['event-name'], l['event-finish'])
    )


num_lanes = 0    # Number of lanes needed so far.
free_lanes = []  # Set of currently unassigned lanes.
event_lanes = {} # Which event gets assigned to which lane.


# Now iterate through all events. If it is a event start event, we
# assign a free lane and insert a finish event. If it is a stop event,
# we add the lane used by the event to the pool again.
while events:
    e = heapq.heappop(events)

    # Event start case.
    if e[1] == EVENT_START:
        # If there is no free lane, increase the number of lanes.
        if free_lanes == []:
            num_lanes += 1
            free_lanes.append(num_lanes)

        # Assign free lane to event
        lane = free_lanes.pop()
        event_lanes[e[2]] = lane

        # Insert event finish event.
        heapq.heappush(
            events,
            (e[3], EVENT_FINISH, lane)
        )
    # Event finish case.
    else:
        # Free lane and add to the pool.
        free_lanes.append(e[2])


# And now we have one lane assigned to each event:
for k, v in event_lanes.items():
    print('Event %s is assigned to lane %s' % (k, v))