Help with mergeing data algorithm

[cangove]

Ok been racking my brain for an "intelligent" solution to my problem set. I think that I may have frie my brain and msising something obvious. So onward with the asking.

I have a set of time based data. Each piece of data ahs a start time and an end time. The incomming data can overlap, and is not aligned with each other in any way. What I need to do is take this data, and create new set of values, broken down into overlaping bits (adding the values for voerlap, althoguh eventually I may have to average them as well). For example if given:

start end value
0 100 100
25 50 200
50 75 300

I would get
0 25 100
25 50 300
50 75 600
75 100 400

In the simple case above its pretty easy to do by hand. But it gets more difficult as the size of data gets bigger and the overlaps weirder. All of the solutions I come up with are exponential which will not work as I may be dealing with 1million+ data points here. Any ideas on an algorithm?

[evasive]

you will have to assign each chunk an activity pointer and and a value pointer. You then add all pointer values times active/non-active.

Not sure how to code it because programming language not given but I think that's the way to go...

[rilorilo]

Assuming your data has been put into a linked list with the following structure, it would go something like this:

data.start = 0
data.end = 100
data.value = 100
data.next = [next data entry]

code:

Code: Select all

if (data is not sorted)
{ sort(data by start) }

nextdata = data;
while (date.next is NOT NULL) // search the entire linked list
{
 nextdata = datanext.next;
 if (data.end <= nextdata.start)
 {
   data = data.next
   nextdata = data
 }
 else if (data.start = nextdata.start)
 {
   if (data.end >= nextdata.end)
   {
      break data up and insert into sorted linked list
   }
   else
   {
     break data up and insert into sorted linked list
   }
  }
  else if (data.start < nextdata.start)
  {
   if (data.end >= nextdata.end)
   {
      break data up and insert into sorted linked list
   }
   else
   {
     break data up and insert into sorted linked list
   }
 }
}

O(break data up and insert into sorted linked list) = O(log(n))
O(while loop) = O(n(n-1)+(n-1)(n-2) ...) ~ O(n(n+1)n) = O(n^3)
So you have a running time close to O(n^3 * log(n)) for the big loop, and the sort function can be done in like n log n time thus being slower than n^3 * log(n).