# Single machine triangle scheduling

We are given *n* jobs. Each job has a processing time p_{j}.
We have to place the jobs on the time time, job j schedules from time S_{j} to S_{j}+p_{j}. Jobs can overlap but for every i,j we need |S_{i}-S_{j}| ≥ min(p_{i},p_{j}).
The goal is to minimize the makespan.
The problem is strongly NP-hard.

## Input

## Output

The diagram below shows the schedule produced by the greedy algorithm, which is guaranteed to be at most 1.5 times the optimal makespan.

[src]