I came up with the following problem and apparently can't find an effective way to solve it:

Consider $ n $ Customers who arrive at a service point at certain times $ {a_i } _ {i = 1} ^ n $ whose service period (let's say from a single employee) is known

his $ {d_i } _ {i = 1} ^ n $, Choose the type of maintenance so that

the total sum of waiting times (i.e. if we consider $ {s_i } _ {i = 1} ^ n $

the start time for each customer, then the total waiting time

would $ sum limit_ {i = 1} ^ n {s_i-a_i } $) is minimized.

The only difference between this problem and interval planning, which involves choosing the earliest end time first, is that here **all** Customers have to be serviced. (whereas some intervals may not be selected in interval planning)

Is there an efficient greedy algo for this problem? Or isn't there? Many obvious or less obvious approaches don't seem to work, for example:

- Customer 1: Arrival at 1 a.m., duration 9
- Customer 2: Arrival at 2 a.m., duration 13
- Client 3: Arrival at 3pm, duration of $ epsilon $

The example above gives advice on choosing the smallest one $ a_i + d_i $ First, but I don't seem to be able to prove it with an exchange argument … Maybe the problem is NP-Complete?