Resolving the stacking order of overlapping items

Question

I have a list of Foo with these properties:

class Foo
(
    Date From
    Date To
    int Importance
)

The From and To dates of these items can overlap. Where two foos overlap, the foo with the highest Importance overrides the other items.

Is there an elegant algorithm to take a list of Foo and resolve any overlaps (by determining which Foo has the highest Importance factor) using the above rules? My attempts so far have been ugly. Ultimately they come down to a series of checks for each possible overlapping conflict, such as a higher priority preceding a lower priority foo, a higher priority foo appearing in the middle of the range of a lower priority foo, and so on. Such a strategy looks unmaintainable and begs for a more elegant approach that I haven't yet found.

The big issue here is that a higher priority Foo can subdivide a lower priority one, so we can't simply adjust the From and To points of conflicting Foos.

Answer 1

You can use a priority queue.

1. Generate all triples (Date, bool, int), where the first argument is a To or From property of one of the Foos and bool indicates whether it's a To (true) or From (false) and the int one is the priority.
2. Sort the list of those pairs by Date
3. Create an empty priority queue of of triples ordered by Importance.

4. Iterate over the sorted list and for each triple (date, isTo, importance) do:

   a. If it's a From (isTo=false) then add to the queue

   b. If it's a To (isTo=true) then remove from the queue

At any time the max element in the queue (which you can lookup in O(1)) contains the one who wins for that time.

(If you need the actual Foo object, just make the triple a 4-tuple with a reference to the Foo).

Answer 2

I would also use a Priority Queue, just like Petar, but I would simply store all the Foo elements in it. The priority in that queue would be: first - the From date, secondly the To date, thirdly the "priority" (i mean first "sort" all elements according to the from field, then the ones with the same from field according to the to fields and lastsly according to the priority). After you have the priority queue done you can just simply iterate over it checking every pair of elements whether the "distance" between them is the same (where distance would be ( (To1-To2)+(From1-From2) ). If you find such a pair leave the first item and delete the second one. You can actually do that either while creating the queue or during the insertion of a new item. The whole algorithm would be O(nlogn) if I'm correct.

@Edit: oh, sorry I was before my morning coffee, and I thought you meant a situation where 2 Foos have the same To and From, from what I now understand you also want to remove items in situations like:
Foo1 From 5 To 10 Priority 1
Foo2 From 1 To 11 Priority 2
What is the "enclosing" Foo (ie 1-11) has a lower priority?

@Edit2: well ok still my algorithm with a slight adjustment should work. Instead of t1-t2+f1-f2 just order them as i mentioned above and check each pair whether F2 (from from foo2) is between T1 and F1. If yes then remove Foo2.

Example:
Foo1: From 3 To 4 Priority 1
Foo2: From 5 To 6 Priority 2
Foo3: From 1 To 7 Priority 3

After prioritizing it would be:
Foo3 -> Foo1 -> Foo2
First you check Foor3 and Foo1, the From of Foo1 is between From and To of Foo3 so you delete Foo1 since it has a lower priority (lets say the better the better in this case). Then you check Foo3 and Foo2 (you'd check Foo1 and Foo2 if it wasnt removed). Again you check whether From of Foo2 is between From and to of Foo3 and, since it is, delete Foo2.
The whole algorithm is still O(nlogn). Give me a shout if I failed to see some cases where it would fail.