Codingame Solution: Super Computer

In the Computer2000 data center, you are responsible for planning the usage of a supercomputer for scientists. Therefore you've decided to organize things a bit by planning everybody’s tasks. The logic is simple: the higher the number of calculations which can be performed, the more people you can satisfy.

Solution

This problem is known as the activity selection problem and can be solved with a greedy algorithm quite easily. We basically read in the time intervals and sort them by their ending dates in ascending order. The first task is part of our final solution. We then pick any new task, which does not overlap with it's previous time interval. The given example looks like this when read in:

When the data is sorted by the end date, the result looks like this and it get's obvious why this algorithm works:

The only thing left is picking the resulting tasks, or simply count them in our case. In Groovy, this can be implemented like this:

input = new Scanner(System.in)

N = input.nextInt()
A = new int[N][2]

for (i = 0; i < N; i++) {
    J = input.nextInt()
    D = input.nextInt()
    
    A[i][0] = J
    A[i][1] = J + D - 1
}

Arrays.sort(A, new Comparator<int[]>() {
    int compare(int[] a, int[] b) {
        return a[1] - b[1]
    }
})

num = 1
lim = A[0][1]

for (i = 1; i < N; i++) {

    if (lim < A[i][0]) {
        lim = A[i][1]
        num++
    }
}
println num