Super Computer


This puzzle is a scheduling problem. Given the start and end dates of several events, you have to compute the maximum number of events that will be able to take place without overlapping. A well know algorithm, Earliest Deadline First running in O(n log n) gives the optimal schedule, then you only have to count the total number of scheduled events.

Python

# Stores each calculation start and end dates, then sorts calculation by end date
calcs, lastCalc, result = [], 0, 0
for i in range(input()):
    start, duration = [int(j) for j in raw_input().split()]
    calcs.append((start, start+duration))
    lastCalc = max(lastCalc, calcs[i][1])
    
calcs.sort(key=lambda c: c[1])

# fill a timeline in which a free day is a 0, and a busy day a 1 with EDF
timeline = [0] * lastCalc 
for c in calcs:
    if not 1 in timeline[c[0]:c[1]]:
        result += 1
        timeline[c[0]:c[1]] = [1] * (c[1]-c[0])

print(result)