CODEWITHSUNDEEP
algorithminterval-tree
Jeroen
Jeroen

Reputation: 1638

find intervals not in tree

I have a bunch of (date)intervals which might overlap. The intervals come from different sources. I want to 'flatten' this 'timeline' and then find all intervals where no interval was.

If you look at: http://www.dgp.toronto.edu/people/JamesStewart/378notes/22intervals/ to the "A more complex example" section. I thus want to find the intervals where no composer was alive.

How do I do that? and how would you implement such a thing in PHP? Does PHP also have some easy functions for building the tree?

many thx!

edit My input is a number of arrays (2, 3 or 4) with each containing start and stop dates like so: 

 $myarray1[0]['start']['date'] = 'somedate'
 $myarray1[0]['stop']['date'] = 'somedate'
 $myarray1[1]['start']['date'] = 'somedate'
 $myarray1[1]['stop']['date'] = 'somedate'
 $myarray1[2]['start']['date'] = 'somedate'
 $myarray1[2]['stop']['date'] = 'somedate'

the same goes for myarray2, myarray3 and so

Upvotes: 2

Views: 206

Answers (2)

oleksii
oleksii

Reputation: 35935

A simple algorithm in steps

  1. Define a function that translates a date object to an integer (and vice versa). This is a place where you may need to optimize the translation to make all numbers as small as possible. A date from past must have smaller number then a date from future

  2. Initialize array of numbers. Set all bits to 0. Make sure the size of the array matches the largest date number (from step 1).

  3. Iterate over the date ranges

  4. Mark date range in the array with 1s. Use date translated into a number (step 1) as an index in the array.

  5. Translate all indexes with 0s back to the date intervals.

Runtime complexity O(N). Space complexity O(N).

Upvotes: 1

hcarver
hcarver

Reputation: 7234

Basic algorithm

For each composer, create two objects. One is a birth object with the composer's name and the year of birth. The other is a death object, again with the composer's name and the year of death.

Now sort these objects together.

Keep an int, initialised to 0 for num_composers_alive.

Iterate through the ordered list of objects. Every time you encounter a birth object, increment num_composers_alive. Every time you encounter a death object, decrement num_composers_alive.

While incrementing or decrementing, every time you hit a death and decrement, check if num_composers_alive went to 0. If so, you just entered a period when no composer was alive. Output that number or store it somewhere. Every time you hit a birth and increment, check if num_composers_alive is now 1. If so, you just ended a period when no composer was alive. Output that number or store it somewhere.

Implementation

This is going to depend on the form of your input and output. I don't believe PHP has a native concept of trees, but I might be wrong on that. Try implementing the above, and open a separate question if you get stuck.

To be honest, I'm not sure why you need trees to solve the above problem anyway, but maybe it's for something else.

Upvotes: 3

Related Questions