1 Attachment(s)

Help understanding how to write this algorithm

I'm trying to work through an algorithm textbook and I've come across this problem that seems very vague to me and I'm very stuck. Can anyone walk me through it to help me understand how problems like these are to be solved? It's supposed to be done in O(n log n) time but I barely understand what that means...

Here it is:

Attachment 29440

Re: Help understanding how to write this algorithm

Hey Donna654.

With problems like these, the best thing to do is to draw a diagram. In this problem you have a straight path, but it is broken into segments.

So now you have an array of segments: each jogger has their own array of segments and we assume that they only run on one local track each (i.e. the jogger runs on say segment 2-4 but they don't go on say 2-3 then skip 4 and then run on segment 5).

So basically you have a min and max value for the segments that a particular jogger runs and now you have to identify the actual segments that need a billboard.

So for your data structure is an array of pairs: each item corresponds to a joggers start and end segment. You have to use that info to detect which segments need a billboard.

I'll ask you to attempt to write some pseudo-code that includes the conditions for going through the pairs and then checking what segments are required for a billboard for that given pair.