CODEWITHSUNDEEP
algorithmoptimizationdata-structurestime-complexity
Loqa
Loqa

Reputation: 79

Optimizing the given problem to linear time without worrying about space

Given a list of meeting start time and end time of people's schedules, find the number of people in given time. The time would be given as integers. For example:

Input is 

[ [ 12, 14] ,[12,15],[14,16],[13,15]]

Output should return 

[ 0,0,0,0,0,0,0,0,0,0,0,2,3,4,3,1]

How to do in linear time?

I can do it in O(n*m).

To find each of the output , scan the input and find the total number of people in given time. That takes O(n*m) n = size of input , m = size of output

Upvotes: 1

Views: 56

Answers (2)

Matt Timmermans
Matt Timmermans

Reputation: 59253

The trick for doing this in O(n+m) time is:

  1. Find the size of the output array required (O(n) time)
  2. Allocate the out array and fill it with zeros (O(m) time)
  3. For each [a,b] in the input, out[a]+=1; out[b+1]-=1 (O(n) time)
  4. Replace each element in the output with the cumulative sum of all elements up to that point. (O(m) time). For example for (int i=1; i<out.length; ++i) out[i]+=out[i-1];

Upvotes: 1

Gene
Gene

Reputation: 46990

The obvious algorithm does pretty well:

def schedule(spans):
  s = [0] * max(map(max, spans))
  for lo, hi in spans:
    for t in range(lo - 1, hi):
      s[t] += 1
  return s

print str(schedule([[12, 14],[12,15],[14,16],[13,15]]))

This is O(L + n) where L is the total length of all the spans and n is the size of the output.

Then:

$ python foo.py
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 2, 3, 4, 3, 1]

Now if you have many overlapping intervals, then you can use a 1d sweep line algorithm to calculate the result on O(n log n + m) time where n is the number intervals and m is the number of output time units.

Something like this, though I won't at all claim this is fully correct: 

def schedule_faster(spans):
  events = []
  for lo, hi in spans:
    events.append((lo, '+'))
    events.append((hi + 1, '-'))
  events.sort()
  s = [0] * max(map(max, spans))
  n = 0
  t_last = events[0][0]
  for t, dir in events:
    if t != t_last:
      for i in range(t_last - 1, t - 1):
        s[i] = n
      t_last = t
    n += 1 if dir == '+' else -1
  return s

Actually if you use a radix sort or other pseudo-linear time sorting algorithm then this becomes O(n + m) in practice.

Upvotes: 0

Related Questions