Generally what kind of algorithm is used to solve when dealing with overlapping data sets .

In the below problem set, we can see that region (point 2 to point 3) is common to both statement A and statement B.

Problem Set

Statement A : Point 1 to 3 --> Speed is 30kmph
Statement B : Point 2 to 5 --> Speed is 50kmph

Goal is to reorganize the data by splitting the common data ranges and calculating the averages and show them as below.

Expected result :

1 to 2 -> 30 kmph
2 to 3 -> (30 + 50)/2 -> 40 kmph
3 to 5 -> 50 kmph
  • Why -1? Pls bother to leave a comment. – mk.. Jun 28 '16 at 23:27
  • 2
    I'm not even sure I understand your problem statement. I suspect that it is not fully specified, but even if it is, the correct algorithm to solve the problem is the one you write. – Robert Harvey Jun 28 '16 at 23:29
  • @RobertHarvey Ok, I will try editing it to make it understandable. The question is that how do we solve the problem when the data regions are overlapping. in the above problem , region 2 to 3 is common to both 1 to 3 and 2 to 5. So in this case i need to take the average of their corresponding values. My selection of example may not be good.. but pls try to understand what is my question regarding algorithm. I am sure there must be some standard algorithm to achieve this.. – mk.. Jun 28 '16 at 23:34
  • 1
    Based on your stated problem, the speeds are fixed, not an average (mathematical mean). This would mean that the average you are calculating would be impossible as you can't both be travelling at 30 kph and 50 kph at the same time. – Adam Zuckerman Jun 29 '16 at 0:04
  1. Keep segments in sorted order (list, binary tree, whatever...)
  2. When adding a new segment, search list, binary tree, whatever to see if it either end of the new segment overlaps an existing segment. If it does, remove/split into new set of segments according to your combining rule (in your example, averaging the overlapping parts).

I don't think there is a standard approach as too much will depend upon the actual application. (Mixing sound according to cues, temporal logic, etc.)

For small problems, a sorted linked list of non-overlapping segments would suffice. There are lots of interesting edge cases to be tested, whatever your implementation.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.