Coding Solution

Super Computer – CodinGame solution in Python

Hardgreedyinterval schedulingsortingUpdated
Short answer

Super Computer is the classic interval scheduling problem: turn each request into a half-open interval [J, J+D), sort the intervals by end day, and scan them once, keeping a request whenever it starts on or after the end of the last request you kept. The number of kept requests is the answer, and the greedy choice of 'earliest finish first' is provably optimal.

The problem

A laboratory has one supercomputer and a list of N reservation requests. Each request starts on day J and lasts D consecutive days, so it occupies days J to J+D-1. Two requests cannot share any day. You must print the largest number of requests that can be accepted together.

N can reach about 100,000, start days go up to roughly one million and durations up to about a thousand days, so anything quadratic in N, or anything that walks every day of every request in a slow language, risks a timeout on the biggest tests.

Approach, step by step

  1. Model each request as a half-open intervalStore a request as (start, end) with end = J + D. Using an exclusive end removes every off-by-one question: a request ending at 10 and another starting at 10 do not overlap, because the first one's last day is 9.
  2. Sort by end daySort all intervals by their end value. Ties and start order do not matter for correctness; only the end day drives the greedy choice.
  3. Greedy scan with one variableKeep free_from, the first day the machine is free (initially 0). For each interval in sorted order, accept it if start >= free_from, then set free_from = end. Otherwise skip it.
  4. Why earliest finish is optimalTake any optimal schedule and compare it with the greedy one. The greedy first pick ends no later than the optimal first pick, so you can swap it in without creating a conflict; repeating this argument job by job shows greedy never accepts fewer requests.
  5. Print the counterThe number of accepted intervals is the answer. You never need to know which requests were chosen.

Complexity

TimeO(n log n)
SpaceO(n)

Sorting dominates; the scan is a single linear pass. Memory holds the list of intervals and nothing that depends on the size of the calendar.

Solution code

Bug fixed in this version: The Python block uses Python 2 syntax (range(input()) and raw_input()), which raises errors on CodinGame's current Python 3 runtime. Its algorithm is correct, but the day-by-day timeline is heavier than needed; the replacement is a Python 3 version of the same greedy with O(1) extra state.

Super Computer – Python

import sys


def main():
    data = sys.stdin.read().split()
    n = int(data[0])
    jobs = []
    for i in range(n):
        start = int(data[1 + 2 * i])
        duration = int(data[2 + 2 * i])
        # half-open interval [start, start + duration)
        jobs.append((start + duration, start))

    # earliest end first
    jobs.sort()

    count = 0
    free_from = 0  # first day the machine is free
    for end, start in jobs:
        if start >= free_from:
            count += 1
            free_from = end

    print(count)


main()

Common mistakes

Going further

The puzzle is often described as 'Earliest Deadline First', but the deadline wording is misleading: there are no deadlines here, only fixed intervals, and the right name is the activity selection problem. A neat way to convince yourself the greedy is optimal is the 'stays ahead' argument: after k picks, the greedy's k-th accepted job always ends no later than the k-th job of any valid schedule. If an optimal schedule had one more job, that extra job would start after the optimal k-th end, hence after the greedy k-th end too, so greedy would have accepted it. This also tells you that ties in end day can be broken arbitrarily.

FAQ

Is Super Computer a dynamic programming problem?

No. Weighted interval scheduling needs DP, but here every request counts the same, so the greedy earliest-end strategy is optimal and much simpler.

Do two requests overlap if one ends on day 5 and the next starts on day 5?

Yes. A request starting on day J with duration D uses day J+D-1 as its last day, so the next one may start at J+D at the earliest. With half-open intervals the test is simply start >= previous end.

Why does my solution time out on the last test?

Usually because it compares every pair of requests or fills a day-by-day array in a slow language. Sort once and scan once; that handles 100,000 requests instantly.

Similar puzzles

★ 5.0 · 16 reviews · 928 users Add to Chrome