A
A
Alexey Menkov2012-09-10 09:50:21
Algorithms
Alexey Menkov, 2012-09-10 09:50:21

Can you suggest an algorithm for determining the minimum covering range?

Good day!
Given: I have data ranges (parameters), in the format "Start Byte" - "Start Bit" - "Number of Bits". There may be several of them, they may overlap, they do not necessarily go in ascending order of the start byte. I need to make a request in the format "Starting byte" - "Number of bytes", which would cover all ranges of bits (there may be several sections).
It is necessary, accordingly, to come up with an encoding and decorating algorithm that would preserve (or allow restoring) the order of the parameters.
And a few examples:
1) 0-0-5, 0-5-4, 10-3-3 - common ranges would be 0-2 and 10-1.
2) 0-0-1, 0-1-15, 0-0-1, 0-1-15 - general range 0-4.
3) 94-0-1, 104-0-5, 92-0-2, 94-1-1 - general range 94-1, 104-1, 92-1.

So I need to somehow unify it, and unite it under a common comb, can you tell me anything?

Answer the question

In order to leave comments, you need to log in

1 answer(s)
M
MikhailEdoshin, 2012-09-10
@alekseymenkov

Put in a heap by the number of the starting byte (the smallest is the top one), take out the first element, make an element based on it in the final format - this will be the current element. Then, in a loop, take the next element from the heap, see if it intersects with the current one. If yes, modify the current one, if not, pass the current one to the final list (since this is a heap, there are definitely no other intersecting elements), and make a new current element.

Didn't find what you were looking for?

Ask your question

Ask a Question

731 491 924 answers to any question