On Mon, 30 Mar 2009 07:50:49 -0700, pruebauno wrote: > I myself asked about how to write a library to efficiently do union and > intersection of sets containing time intervals some time ago on this > list and got little to no answers. It is a tricky problem.
With all the confidence of somebody who doesn't need to solve it, I can say, no, it's an easy problem, provided you use the correct data structure. What you want is an interval tree: http://en.wikipedia.org/wiki/Interval_tree > Since I was > getting paid I got an O(n*n) solution working. Just off the top of my head, I *think* you should be able to get that down to O(m * log n) where m is the size of one set and n the size of the other. Don't quote me on that though. > People on this list on the other hand do not get paid We don't??? Damn! I was expecting a HUGE cheque at the end of the month! BTW Aaron, I haven't replied to your post about the garbage collector because that's one part of Python programing where I cherish my ignorance. -- Steven -- http://mail.python.org/mailman/listinfo/python-list