-6

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
Improve this question
4
  • Why -1? Pls bother to leave a comment. Commented Jun 28, 2016 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. Commented Jun 28, 2016 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.. Commented Jun 28, 2016 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. Commented Jun 29, 2016 at 0:04

1 Answer 1

Reset to default
1
  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.

Improve this answer

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.