Marzullo’s Algorithm

November 15, 2016

This one is tricky:

Given a list of events with arrival and departure times, write a program that determines the time at which the greatest number events occurred.

For instance, you may have ten employees who arrived at work and departed at the times shown below (for instance, employee 9 arrived at 12:00noon and departed at 5:00pm):

employee   1  2  3  4  5  6  7  8  9 10
          -- -- -- -- -- -- -- -- -- --
arrival   10 12 11 13 14 12  9 14 12 10
departure 15 14 17 15 15 16 13 15 17 18

Then the maximum employee count was at 2:00pm:

 9 |                    7          | 1
10 |  1                 7       10 | 3
11 |  1     3           7       10 | 4
12 |  1  2  3        6  7     9 10 | 7
13 |  1  2  3  4     6  7     9 10 | 8
14 |  1  2  3  4  5  6     8  9 10 | 9
15 |  1     3  4  5  6     8  9 10 | 8
16 |        3        6        9 10 | 4
17 |        3                 9 10 | 3
18 |                            10 | 1

There were 9 employees at work at time 14.

Your task is to write a program that determines the start and end times of the time block where the greatest number of events occurred. When you are finished, you are welcome to read or run a suggested solution, or to post your own solution or discuss the exercise in the comments below.

Pages: 1 2

3 Responses to “Marzullo’s Algorithm”

  1. Rutger said

    In Python. Probably should have used the collections.Counter, but this will do.

    arrivals = [10,12,11,13,14,12,9,14,12,10]
    departures = [15,14,17,15,15,16,13,15,17,18]
    
    counts_per_hour = [0]*(max(arrivals+departures)+2)
    
    for arrival, departure in zip(arrivals, departures):
    	counts_per_hour[arrival] += 1
    	counts_per_hour[departure+1] -=1
    print counts_per_hour
    
    number_of_events = 0
    for i,v in enumerate(counts_per_hour):
    	number_of_events += v
    	print 'At hour', i, ': the number of events is', number_of_events
    
    

    Outputs:
    At hour 0 : the number of events is 0
    At hour 1 : the number of events is 0
    At hour 2 : the number of events is 0
    At hour 3 : the number of events is 0
    At hour 4 : the number of events is 0
    At hour 5 : the number of events is 0
    At hour 6 : the number of events is 0
    At hour 7 : the number of events is 0
    At hour 8 : the number of events is 0
    At hour 9 : the number of events is 1
    At hour 10 : the number of events is 3
    At hour 11 : the number of events is 4
    At hour 12 : the number of events is 7
    At hour 13 : the number of events is 8
    At hour 14 : the number of events is 9
    At hour 15 : the number of events is 8
    At hour 16 : the number of events is 4
    At hour 17 : the number of events is 3
    At hour 18 : the number of events is 1
    At hour 19 : the number of events is 0

  2. matthew said

    Here’s some Javascript. Also an example of random intervals (possibly more like the NTP usage with less intervals with common start/end points).

    const f = (arrivals,departures) =>
          arrivals.map(t => [t,-1])
          .concat(departures.map(t => [t,1]))
          .sort(([t1,s1],[t2,s2]) => t1==t2 ? s1-s2 : t1-t2)
          .reduce(([n,maxn,max,maxend],[t,s],i,a) =>
                  (n => n <= maxn ? [n,maxn,max,maxend]
                   : [n,n,t,a[i+1][0]])(n-s),
                  [0,0,0,0])
    
    const arrivals =    [10,12,11,13,14,12, 9,14,12,10]
    const departures1 = [15,14,17,15,15,16,13,15,17,18]
    const departures2 = [15,15,17,15,15,16,15,15,17,18]
    console.log(f(arrivals,departures1))
    console.log(f(arrivals,departures2))
    const data =
          (a => [a.map(s => s[0]), a.map(s => s[1])])
          (Array(6).fill()
           .map(_ =>((x,y)=>[Math.min(x,y),Math.max(x,y)])
                    (Math.random(),Math.random())))
    console.log(data)
    console.log(f.apply(null,data))
    
  3. V said

    In Ruby

      
    def time_block_with_most_events(events)
      min_t, max_t = events.flatten.minmax
      
      events_on_times = (min_t..max_t).map do |t|
        [ t, events.select { |x, y| t.between?(x, y) }.count ]
      end
      
      max_events  = events_on_times.map { |t, c| c }.max
      time_blocks = events_on_times.select { |t, c| c == max_events }.map(&:first)  
      [max_events] + time_blocks.minmax
    end
    
    arrivals    =  [10,12,11,13,14,12, 9,14,12,10]
    departures1 =  [15,14,17,15,15,16,13,15,17,18]
    departures2 =  [15,15,17,15,15,16,15,15,17,18]
    
    time_block_with_most_events(arrivals.zip(departures1))
    => [9, 14, 14]
      
    time_block_with_most_events(arrivals.zip(departures2))
    => [10, 14, 15]
    
    

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: