Filtering list items with time complexity of O (n)

Question

I have a list of elements where each element is a non-negative integer. I want to filter the list so that only the largest unclosed ranges stand out. And I want to do this with O(n) with one loop. This list will always be sorted according to the starting integer for each range. A limited range element may occur before or after an environment element in a list.

Example:

Suppose I have a list of {[0-12],[5-15],[5-20],[10-20],[11-30],[25-42],[28-40]} . In this list, ranges [5-15] and [10-20] fall into the range [5-20] , so I need to drop them. Similarly, a range element [28-40] discarded when it falls into a range [25-42] . I want to do this filtering using a single loop to achieve O(n) time complexity.

Is it possible to achieve this? If not, then a better way to make filtering more complicated than O(n) . A Java solution would be great.

Answer 1

An element can learn the previous one if they have the same start, but are greater than or equal. Also, an element can learn the next if the next one range ends less than the current end of the element.

So, you are browsing the list and comparing the current and next items.

If they have currentStart = nextStart and nextEnd> = currentEnd -> delete the current one.

else If nextEnd <= currentEnd → delete the next.

Answer 2

in pseudo code, merge periods can be performed as follows:

 def merge(l:list[period], e:period): if l == nil: return list(e) else: lh = l.head ll = l.tail if e.end < lh.start: return e::l // original list prepended with e else if lh.end < e.start: return lh::merge(e,ll) // head + trying to merge period with the tail else: //overlap, make new period from e and list head and merge it with tail newstart = min(e.start, lh.start) newend = max(e.end, lh.end) return merge(period(newstart,newend), ll) 

In your case, you need to do an i / o merge, but the idea is similar.