hi, I have the following problem which is turning out to be non-trivial. I realize that this is not exactly a python problem but more of an algorithm problem -- but I post it here because I want to implement this in python.
I want to write a code that given an interval (integer tuple: start,stop) will find which other interval it matches to. Here is an example, suppose I have the following NON-OVERLAPPING intervals 10 - 21 ==> 'a1' 34 - 51 ==> 'a2' 77 - 101 ==> 'a3' etc So, suppose I'm give an interval such as (42,50), I should go through the list and map it to "a2" etc if the region is a subset of an exiting interval. If the query interval does not exist in the table or maps to two or more intervals (eg, (45, 80)) the program return a None. One naive way to solve this problem is to create an array such as follows: [None, None, None, ...., None, a1, a1, a1, ..., a1, None, None ..., None, a2, ... etc] at indicies 1 2 3 9 10 11 12 21 22 23 33 34, ... now with this in place I can easily solve the problem. However, this is not a feasable solution because the initial list has intervals whose range can go to billions! So I need a smarter idea. So what I can do is sort the initial list and then go through each element from the start and test if the a > X[i][0] and b < X[i][1] where (a,b) is my query start and stop and X is a n x 2 array with the known intervals. I don't like this solution because it can be really really slow as for each query I'm doing a linear search and on average I'll be searching almost half the list before I find the right interval. Is there a smarter way to do this? I've my problem is not clear please let me know and I'll try to explain the unclear parts again. Many thanks Lee -- http://mail.python.org/mailman/listinfo/python-list
