Get breaks from a list of times

Question

I have a list of work items. Each work item has a start and an end time.

So, basically it looks like this:

List<Work> works = new List<Work>();
works.Add(new Work(
  new DateTime(2013, 4, 30, 9, 0, 0),
  new DateTime(2013, 4, 30, 11, 0, 0));

Now I want to get the total time that was worked. Again, basically this is easy:

09:00-11:00 => 2 hours
13:00-17:00 => 4 hours
----
06:00 hours

It's just the sum.

But now it gets difficult: How do I calculcate this sum if I want to extract parallel times?

E.g.,

09:00-11:00 => 2 hours
10:00-11:30 => 1.5 hours
13:00-17:00 => 4 hours
----
06:30 hours

is 6.5 hours, but the sum is 7.5 hours. The fact that two work items map to the time between 10 and 11 o'clock makes the difference.

How could I solve this for an arbitrary number of work items that can overlap each other in basically every possible way (surrounding, start overlaps, end overlaps, including)?

Answer 1

Create pairs of (time, value), where value is +1 for begining of work and -1 for end. Then sort the pairs by date. Iterating the list you got, you can calculate the sum of values - when it is positive, the work is "going on". While iterating, mark the moments when sum of values goes from 0 to positive and from positive to 0. You will get disjoint intervals.

Example:

11 - 13, 12 - 16, 15 - 17, 18 - 19

gives you (11, 1) (12, 1) (13 -1) (15, 1) (16, -1) (17, -1) (18, 1) (19, -1)

the sum goes (11, 1) (12, 2) (13 1) (15, 2) (16, 1) (17, 0) (18, 1) (19, 0),

so the disjoint periods are (11, 17) and (18, 19)

Answer 2

Hmm, I've once solved similar problem (not with times, but with ranges overlaping). Solution I applied was pretty straightforward:

1. Sort elements in ascending order
2. Starting from first element, see if it is overlapping with next element
3. If it is - reprocess elements, extract overlaping section as new element, modify old elements to end before/start after overlapping period
4. Insert newly created element in between two old elements
5. Continue processing

It should work fine, however if you have huge amounts of data there may be better way to solve it. It's just the simplest approach (at least for me). You will end up with list of times with no overlapping sections, so you will be able to just iterate over the list and summarize times.