Filtering out list elements with O(n) time complexity

Question

I have a list of elements, where each element is a non-negative integer range. I want to filter the list in such a way that only largest unenclosed ranges are separated out. And I want to do this in O(n) manner with single loop. This list will always be sorted according to starting integer of each ranges.An enclosed range element may occur before or after the enclosing range element in the list.

Example:

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

Would it be possible to achieve this ? If not, what is the best way to do filtering with complexity more than O(n). A solution in Java would be great.

Answer 1

An element could swallow previous one if they have the same range start but bigger or equal end. Also the element could swallow next if the next one's range end less than current eleemnt's end.

So you go through the list and compare current and next elements.

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

else If nextEnd<=currentEnd -> remove next.