Finding the sum of time for overlapping values

Question

I have been struggling with this question for a couple of days. I have one machine which can have errors. In a database I have the starting and ending time (in unix time) when the error appeared, and the type of error (number from 5-12). The problem I'm having is that multiple errors can occur at the same time (and overlap).

My table looks like this:

   id| type | from       | to
    1| 6    | 1417179933 | 1417180006
    2| 6    | 1417180035 | 1417180065
    3| 9    | 1417180304 | 1417180409
    4| 6    | 1417180662 | 1417184364
    5| 8    | 1417180662 | 1417186832
    6| 9    | 1417180662 | 1417184364
    7| 12   | 1417180662 | 1417184364
    8| 6    | 1417184364 | 1417186832
    9| 9    | 1417184364 | 1417188054

I need to find the total duration of errors for this machine. I can't sum all differences from the above table since it's possible that two or more errors appeared in the same time interval. Records are sorted in ascending order.

My guess was to compare each record (start and finishing time) with previous and then find the difference in seconds. However, this table can grow over time and it is a problem to search through it.

Is there a clever way in PHP or MySQL to find total time where the machine didn't work, possibly in minutes?

Answer 1

Here's a general approach to summing intervals taking into account potential overlaps, supposing intervals are sorted on their lower value.

2 intervals case

When adding two intervals [a,b] and [c,d], thus (d-c) + (b-a) you count their overlap twice.

• If the overlap is non-zero, then its value is min(b,d) - max(a,c). Since you sorted items on the start of the interval, then you know that max(a,c) == c.

• If the overlap is 0, a <= b <= c <= d so min(b,d) == b, max(a,c) == c, and min(b,d) - max(a,c) == b - c <= 0. You awlays want to remove 0 however.

Thus a general formula is d-c + b-a - max(0,min(b,d)-c)

Generalizing to more intervals

To generalize to more intervals than two, just consider that when you add a new interval [c,d] to any number of previous intervals, you add (d-c) and the overlap that is counted twice is between [c,d] and the union of all previous intervals.

Since you sort intervals on their start values, you only need to consider the last continuous interval of this union, thus for you the last continuous period of downtime.

If [a,b] is your previous last continuous interval and you've just added [c,d]:

• If [a,b] and [c,d] overlap, your last continuous interval becomes [a, max(b,d)] because this is the union of [a,b] and [c,d]
• If [a,b] and [c,d] do not overlap, your last continuous interval becomes [c, d] (NB: we have max(b,d) == b)

Since a < c because of sorted intervals, the intervals overlap iff c < b

In code

That is probably easier to implement in php than mysql. In pseudo code, assuming each row returns a (start,end) error interval, and [a,b] is your last known continuous interval:

(a,b) = get_first_row();
downtime = b-a;
while( (c,d) = get_next_row() )
{
     downtime += d-c - max(0, min(d,b)-c);
     a = c < b ? a : c;
     b = max(b,d);
}

You can see this code run successfully here : https://3v4l.org/Q2phs