On Aug 13, 5:49 am, Arthur Milfait <a...@gmx.info> wrote:
> hi there,
>
> actually i am programming a software that loads numbers for radios in
> a trunking system from a file and has to check each number if it is a
> number for a group of radios. criterion to be the number of a
> radiogroup is, that the number is within an interval from an including
> lower limit to an excluding upper limit. there can be several of these
> intervals AND the intervals can be overlapping.
>
> numbers can be provided sorted (requires a sort-operation first).
> intervals can be provided sorted (by lower or upper limit) and of
> course overlapping intervals can be merged first
>
> eg.
> numbers N1 to Nn
> intervals I1 to Im
>
> problem: is Nx in Iy for all x=1 to n and y= 1 to m
>
> how can i solve this in the most efficient manner?
> is there a way to keep an algorithm for that problem at least at O
> (log)?
>
Assuming both lists are sorted and the overlapping intervals are
merged
at the start it should be at most O(m+n). Just start at the beginning
of
both lists and loop until you've gone through all the numbers.
Start loop
If no intervals left result is false move to next number
Else If the current number is before the current interval result is
false,
move to next number.
Else if the current number is in the current interval result is true
move to next number.
Else move to next interval.
End loop
Each pass reduces either m or n by 1, worst case m+n iterations,
best case n
--
Geoff
--~--~---------~--~----~------------~-------~--~----~
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To post to this group, send email to algogeeks@googlegroups.com
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com
For more options, visit this group at http://groups.google.com/group/algogeeks
-~----------~----~----~----~------~----~------~--~---
