I'm trying to find a faster way to filter my list of ranges, so that any range that can be covered completely by a larger range will be excluded. For example,

```
#all ranges have width >1, which means no such case like xx=[1,1] in my list
#each range itself is sorted. E.g. no such case like [1,3,2]. It is already like [1,2,3]
#each range only contains continuous integers. E.g. no such case like [3,5,7], it will only be like [3,4,5,6,7]. In fact, you could simply consider the first and last integer of the range to know the whole range.
aa=[1,2,3]
bb=[2,3,4]
cc=[1,2]
dd=[0,1,2]
RangeList=[aa,bb,cc,dd]
#FinalList=[aa,bb,dd]
```

cc can be covered by aa or dd (I consider it as a subset), so I'd like to exclude it. I definitely could write a loop for n^2 comparisons, but I would appreciate a faster method, since I have a lot of these ranges.

# Best How To :

You can solve this by sorting first:

```
import operator
ranges=[[0,1,2,3,4], [1,2], [0,1], [2,3,4], [3,4,5], [3,4,5,6], [4,5], [6,7], [5,6]]
sorted_ranges = sorted(ranges,key=operator.itemgetter(-1),reverse=True)
sorted_ranges = sorted(sorted_ranges,key=operator.itemgetter(0))
filtered = []
i,j = 0,0
while i < len(sorted_ranges):
filtered.append(sorted_ranges[i])
j = i+1
while j < len(sorted_ranges) and sorted_ranges[i][-1] >= sorted_ranges[j][-1]:
print "Remove " , sorted_ranges.pop(j) , "dominated by",sorted_ranges[i]
i+=1
print "RESULT",filtered
```

You will need to sort on the first element in ascending order and descending order for the last element. I used two explicit calls of sorted but you could define your cmp function to do this in one pass:

```
sorted_ranges = sorted(ranges,cmp=lambda x,y: (x[0]-y[0]) if ((x[0]-y[0]) != 0 ) else (y[-1]-x[-1]))
```

In this way dominating ranges will appear first. Notice that the nested while loop after sorting has complexity O(n) since each element is examined only once and either removed or added to the final set. Complexity of the whole algorithm is O(nlogn)