Update 12/17/2016: I was looking through some old stuff and found this once again. To be honest, my original solution to this had always seemed iffy, not at all the way I’d imagined it to be. It seemed unnecessarily bulky. So I had another shot at it, this time sticking with my original algorithm, and came up with the following:

def answers(intervals):
    fin = []
    for i in sorted(intervals,key=lambda x:x[0]):
        for k,j in enumerate(fin):
            if max(i[0],j[0]) <= min(i[1],j[1]): # check if overlapping
                fin[k] = [min(j[0],i[0]),max(j[1],i[1])]
                break
        else:
            fin.append(i)
    return sum(abs(a-b) for a,b in fin)

The large amounts of sleep I’ve gotten in the calm before the storm (ie. finals week) must have done wonders for my mind, because I came up with this solution in ten minutes. Granted, I don’t have access to the challenge itself to test against, but the few cases I recorded in my post below seem to work. All in all, I am much happier about this solution.

Reasons why this is a better solution:

  • no importing any modules
  • pretty simple algorithm not requiring a whole page to explain
  • for-else. I’ve always wanted to use it but could never find a place for it
  • shorter!!

The below will be kept for historical purposes.

import bisect
def answer (intervals):
    s = intervals[0]
    for i in range(1,len(intervals)):
        si = bisect.bisect_left(s,intervals[i][0])
        ei = bisect.bisect_left(s,intervals[i][1])
        if si % 2 == 0:
            if ei % 2 == 0:
                s[si:ei] = intervals[i]
            else:
                s[si:ei] = [intervals[i][0]]
        else:
            if ei % 2 == 0:
                s[si:ei] = [intervals[i][1]]
            else:
                s[si:ei] = []
    return sum([x for i,x in enumerate(s) if i % 2 == 1]) - sum([x for i,x in enumerate(s) if i % 2 == 0])

The original text of the problem is as follows:

The first successfully created zombit specimen, Dolly the Zombit, needs constant monitoring, and Professor Boolean has tasked the minions with it. Any minion who monitors the zombit records the start and end times of their shifts. However, those minions, they are a bit disorganized: there may be times when multiple minions are monitoring the zombit, and times when there are none!

That’s fine, Professor Boolean thinks, one can always hire more minions… Besides, Professor Boolean can at least figure out the total amount of time that Dolly the Zombit was monitored. He has entrusted you, another one of his trusty minions, to do just that. Are you up to the task?

Write a function answer(intervals) that takes a list of pairs [start, end] and returns the total amount of time that Dolly the Zombit was monitored by at least one minion. Each [start, end] pair represents the times when a minion started and finished monitoring the zombit. All values will be positive integers no greater than 2^30 - 1. You will always have end > start for each interval.

For example, given the input [[1,3],[2,6]], you have 2 hours from 1-3 and 4 hours from 2-6, but since you double counted the hours from 2-3, the answer is actually a group total of 5 hours.

The intuitive way to do this (as in, the first time I tried to solve this problem) is to loop over ever pair of intervals and, if they overlap, then merge them into one bigger interval:

for i in range(len(list)):
    for j in range(i+1, len(list)):
        if theyOverlap(list[i], list[j]):
            merge(list[i],list[j])

Then (if you do it right) you’re left with a bunch of intervals that aren’t overlapping, so you can just add the times without worrying about over counting. However, sometimes a merge will allow an interval to be merged with a perviously checked interval:

check 1: [ [4,18] , [19,20] , [13,20] ]
             ^         ^                    do not overlap (skip merge)

check 2: [ [4,18] , [19,20] , [13,20] ]
             ^                   ^          overlap (merge)

exit: [ [4,20], [19,20] ]
          ^        ^                        mergeable! (but program has exited loop)

and so I’d get the over counting problem that I jumped through all these hoops (loops, heh) to avoid in the first place. Now, I know there’s probably a trivial solution to this annoyance, but I didn’t want to think, so I searched for a different way.

I created an empty 1D array that represents the timetable for at least one minion monitoring Dolly, and iteratively merged each interval into this array (actually, doing it this way instead of looping through each pair of intervals would have probably solved the problem I was having with my original attempt). Since that was awful wording and you’re probably just confused, here’s an example:

input list : [ [4,18], [19,20], [13, 20] ]
final: [] --> this means that there is no time interval for which at least one minion is monitoring Dolly

loop 1:
next interval: [4,18]
new final: [4,18]           --> this means that before 4, there are no minions
                                                between 4 and 18, there is at least one,
                                                after 18, there are no minions

loop 2:
next interval: [19,20]
new final: [4,18,19,20]     --> this means that before 4, there are no minions
                                                between 4 and 18, there is at least one,
                                                between 18 and 19, there are no minions,
                                                between 19 and 20, there is at least one,
                                                after 20, there are no minions

loop 3:
next interval: [13,20]
new final: [4,20]           --> this means that before 4, there are no minions
                                                between 4 and 20, there is at least one,
                                                after 20, there are no minions

Since this list represents a timetable, it is always sorted, and so using Python’s bisect library, it is simple enough to find out for a given element the index at which it should be inserted to preserve the order. For example, bisect.bisect_left([1,3,7,10],5) == 2 because:

  0   1   2   3
[ 1 , 3 , 7 , 10 ]
        ^
        5 belongs here (at index 2)

It turns out that the parities (whether a number is even or odd) of the indices of the start and end times of the next interval are enough to determine whether or not to merge the interval into a preexisting interval, or to leave it alone. See:

next interval: [2,8]

  0   1   2   3
[ 1 , 3 , 7 , 10 ]
    ^       ^
    2       8
    1       3

Since both of the indices are odd (1 and 3), all you have to do is get rid of everything in between (trial and error to figure out each of the four cases). This yields [ 1 , 10 ], which is the correct result! You know that there is at least one minion from 1 to 3, and the 2-8 minion will cover the time from 3 to 7, and at least one minion is working from 7 to 10, so there is at least one minion working from 1 to 10.

And the best part, it only loops through the input list once! No crazy backflips to catch possibly missed merges.

The green “all test cases passed.” text in the Foobar terminal was so worth the hour of debugging.