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.
Programming Praxis 
In Python. Probably should have used the collections.Counter, but this will do.
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
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))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]MUMPS V1.66 for Linux x86_64 Built Feb 27 2017 at 17:12:15
marzullo ;New routine
n arrivals,departures,end,hour,hours,i,j,max,start
s arrivals=”10,12,11,13,14,12,9,14,12,10″
s departures=”15,14,17,15,15,16,13,15,17,18″
s hour=99,max=0
f i=1:1:$l(arrivals,”,”) d
. s start=$p(arrivals,”,”,i),end=$p(departures,”,”,i)
. f j=start:1:end d
. . s hours(j)=$g(hours(j))+1
. . s:hours(j)>max max=hours(j),hour=j
w !,”There were “,max,” employees at work at time “,hour
q
d ^marzullo
There were 9 employees at work at time 14
sources (ones which do not overlap the optimal interval returned) is the number of sources minus the value of best. Marzullo’s algorithm is efficient in both space and time. The asymptotic space usage is O(n), where n is the number of sources. In considering the asymptotic time requirement the algorithm can be considered to consist of building the table, sorting it and searching it. Sorting can be done in O(n log n) time, and this dominates the building and searching phases which can be performed in linear time. Therefore, the time efficiency of Marzullo’s algorithm is O(n log n) .