I am currently working on a tricky problem at work. I googled around a bit, but "time intervals" did not come up with anything useful. Although I have some rough idea of how I could solve it, I still would value some input.
I have information of (It has only couple dozen entries.) ServiceNum, DollarCost and a input database table in the form (several GBytes): ClientNumber (CN), BeginDate(BD), EndDate(ED), ServiceNumber_Purchased(SN) --Date intervals are always [closed, closed] The output is: ClientNumber(CN), BeginDate(BD), Enddate(ED), DollarCost(DC) With the following requirements: 1) The input dates can be overlapping dates. The output has to be non-overlapping "broken up" dates Example: (assuming SN 1=$10 and SN 2=$20) input (CN, BD, ED ,SN): 10, 1/1/2001,1/1/2005,1 10, 1/1/2002,1/1/2004,2 should result in: output (CN, BD, ED, DC): 10, 1/1/2001, 12/31/2001, $10 10, 1/1/2002, 1/1/2004, $30 10, 1/2,2004, 1/1/2005, $10 2) if the same service is purchased twice for an interval it should be billed only once Example: input: 10, 1/1/2001, 1/1/2005, 1 10, 1/1/2004, 1/1/2007, 1 output: 10, 1/1/2001, 1/1/2007, $10 Here are my thoughts about a solution so far: 1. fetch the input data sorted by clientNumber, Begindate, Enddate and ServiceNumber 2. read the row, store as temporary good interval, then read another row 3. if new begin-date is bigger than previous good interval end-date (or previously saved end-date), output previous good interval, start new good interval 4. else create new good interval entry with good interval begin-date and current row begin-date, store good interval end-date into a list with bisect module or something (so we always compare against smallest end-date). 5. Use "bitwise or" on a service bitfield to add services and caluate the total As you can see my algorithm is a bit scetchy right now, but at this point I am more interested to determine if the bisect module would be the best way to approach the date interval problem or if I should use some other data structure instead (stack, queue, set,...). I am working on a Python proof of concept now. It is likely that the company will want a C++ version of it later (yikes). nes -- http://mail.python.org/mailman/listinfo/python-list
