Sort the interval list A with starting point and then end point. Traverse the list, and skip all the entries

that have end points less than the start point of the target. The results that cover target B are in retVal

There are three conditions to traverse:

starting with the current element skip all the elements that have end points less than the end point of current

element.
if the end point of next element is greater than current end point and if the start point of next element

is less than or equal to target start point or the end point of last element in retVal list than skip current element. and keep skipping until this condition fails
if the last element in the result array has end point greater than the current end point skip the current element.
def compareInterval(i1, i2):
if i1[0] == i2[0]:
return -cmp(i1[1],i2[1])
else: return cmp(i1[0],i2[0])
def maxinterval(alist, i):
alist.sort(cmp=compareInterval)
cnt = idx = 0
start = i[0]
retVal = []
print alist
while idx < len(alist):
v = alist[idx]
if retVal and v[0] > retVal[-1][1]: break
if v[1] <= i[0] or (retVal and v[1] <= retVal[-1][1]):
idx += 1
continue
while idx + 1 < len(alist) and v[1] >= alist[idx+1][1] and alist[idx+1][1] < i[1]:
idx += 1
while idx + 1 < len(alist) and alist[idx+1][0] <= start and v[1] <= alist[idx+1][1]:
idx += 1
v = alist[idx]
retVal.append(v)
idx += 1
start = v[1]
if v[1] >= i[1]: break
return len(retVal) if retVal[-1][1] >= i[1] else 0
if __name__ == "__main__":
alist = [[0,5], [4,20], [5,15], [5,22], [6,21], [7,12], [9,23], [13,25]]
interval = [6,24]
print maxinterval(alist,interval)
alist = [[0,3],[3,4],[4,6],[2,7],[2,6]]
interval = [0,6]
print maxinterval(alist,interval)
alist = [[0,3],[4,7]]
interval = [0,6]
print maxinterval(alist,interval)