## The Goal

## Rules

For example:

Calculation | Starting Day | Duration |
---|---|---|

A | 2 | 5 |

B | 9 | 7 |

C | 15 | 6 |

D | 9 | 3 |

Calculation A starts on day 2 and ends on day 6

Calculation B starts on day 9 and ends on day 15

Calculation starts on day 15 and ends on day 20

Calculation D starts on day 9 and ends on day 11

## Game Input

Line 1: The number `N` of calculations

The `N` following lines: on each line, the starting day `J` and the duration `D` of reservation, separated by a blank space.

`N`< 100000

0 <

`J`< 1000000

0 <

`D`< 1000

## 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
```