# Algorithm to minimize duration

I have times for start and stop and date of service, like this:

2000-01-01 23:00 23:20
2000-01-01 23:50 00:10
2000-01-01 00:20 00:30

The end time of the second period and the third period need to be moved to the next day, so the result would be:

2000-01-01 23:00 2000-01-01 23:20
2000-01-01 23:50 2000-01-02 00:10
2000-01-02 00:20 2000-01-02 00:30

I can not assume that the entries were entered in the order the records are in (so the `2000-01-01 00:20 00:30` entry may not appear after the other two, `00:20` could mean `2000-01-01 00:20` or `2000-01-02 00:20`). Instead, my criterium will be:
Minimize the duration between the minimum start time and the maximum stop time on each day.

In this example:

If I would assume that all times are on 2000-01-01, then the duration between min start time and max end time would be 23 hours (from 00:20 to 23:20). If I move the 2nd and 3rd periods as in my example, the duration between the min start time and max stop time is 1:30 (from 23:00 on 01/01 to 00:30 on 01/02).

Is there some class of algorithms, that would cover this kind of optimization, if not any ideas where to start?

• It sounds like you are actually trying to disambiguate time references, not really optimize anything. e.g. in your first example, the times 23:00 23:20 probably mean (23:00, 1) and (23:20, 1) where "1" is a day number which you can start arbitrarily at "1". On the other hand, 23:50 and 00:10 probably mean (23:50, 1) and (00:10, 2). You can do this programmatically if you assume each new time being delivered is after the previously input one. Of course, if there could be data entry errors, you will probably have to implement some error detection and recovery. – Brandin Sep 20 '16 at 8:53
• No, I can't assume about time delivery, if I could, that would be easy task and that is why I see that as optimization over duration task. – Giedrius Sep 20 '16 at 10:44
• I have rewritten the question (approval pending), please edit further if it is not clear enough yet. I have one question left: why do you allow your duration between the min start time and max stop time is 1:30 calculation, i.e. why is the end time on the next day acceptable? Maybe my on each day edit in the bold requirement needs clarification. – Jan Doggen Sep 20 '16 at 14:20
• Do you get how many people are using their time (and wasting it on answers) because you wrote an unclear question (that includes you, BTW)? Obviously everyone is very friendly in here or you would have gotten downvotes. – Jan Doggen Sep 20 '16 at 14:23
• Are the times paired? Are the times pre designate start or stop? Ie can I use 00:20 as a stop time? – Ewan Sep 20 '16 at 19:37

There are two parts of your problem. The first is that you need to determine the duration of each period. The only real complication there is when period crosses the date boundary. To do that, take the date and put it on both times. If the end time is less than the start, increment the date on the end time by one day.

The second portion of the problem is the minimization operation. Essentially you are seeing which order of the periods creates the smallest span from the start of the first period to the end of the last period. This probably maps to the bin-packing problem and there are lots of algorithms available. I would suggest brute force by trying every ordering if you don't have many periods (less than a few dozen as a guess) to deal with.

Once you have determined the order, the start dates and end dates should follow easily.

The 'date' was in fact a 'business day' which was just a collection of all the things you wanted to account against a particular day and things logged from the till system would just record the time.

So you were left with some odd situations with days over 24h long, daylight savings etc.

But its not really an 'optimisation' to program in the business rules required to change the time into a datetime.

In your case it seems a simple if statement Of :

is end time before start time? Add a day to end time.

• It does not cover case 00:20 00:30 - start is before stop, but it still should be moved to next day to minimize duration between min start to max stop. I updated description I gave example of what optimal solution should be with calculated durations to see the difference. – Giedrius Sep 20 '16 at 13:15
• yes that is a confusing one though. why do you move it to the next day? – Ewan Sep 20 '16 at 13:49
• Ie and not the first one. Sounds like you have an extra rule – Ewan Sep 20 '16 at 16:56
1. order them
2. iterate once
if time this to next delta > last to (time this + 1 day)
then add a day to this
• I respect down and delete but this works – paparazzo Sep 21 '16 at 15:03
• It wasn't me, who downvoted, but I have to agree, that answer is not clear - may be pseudocode or more details would help. – Giedrius Sep 23 '16 at 5:55