Best way of finding the number of people needed [duplicate]

Question

This question already has answers here:

Find the time period with the maximum number of overlapping intervals (4 answers)

Closed 9 years ago.

I have some daily data with the starting time and ending time of an action. Every action requires one person. I want to know how many people I will need.

Here is an example of the data (I am using python):

[str(d.start) + " || " + str(d.end) for d in dailyJobs]

>> ['2013-08-09 07:30:00 || 2013-08-09 11:45:00',
    '2013-08-09 07:25:00 || 2013-08-09 10:45:00',
    '2013-08-09 07:35:00 || 2013-08-09 10:35:00',
    '2013-08-09 09:35:00 || 2013-08-09 12:05:00',
    '2013-08-09 10:15:00 || 2013-08-09 13:20:00',
    '2013-08-09 09:15:00 || 2013-08-09 12:55:00',
    '2013-08-09 12:35:00 || 2013-08-09 15:35:00',
    '2013-08-09 13:05:00 || 2013-08-09 15:25:00',
    '2013-08-09 17:10:00 || 2013-08-09 18:32:44']

Here is a Gantt-chart of the problem:

We can see that 6 actions will be done in the same time. So we will need 6 person.

---

My solution

I could iterate on every minutes and check the number of time ranges I am in. The maximum would be the minimum number of person needed.

I am looking for better algorithm to achieve this.

Answer 1

Let me illustrate my idea, to see if this fits. Let L be an ordered list of non-overlapping time range with a count. Initially L is empty.

For each time range d in dailyJobs, d may overlap with SOME time range in L.

For example:

 L: [ c  ][     c    ][ c ][        c       ]
 d:           [                  ]

Results:

 L: [ c  ][c ][c+1   ][c+1][c+1  ][   c     ]

That is merging L and d s.t. L continues to be an ordered list of non-overlapping time range. After iterating all d in dailyJobs, walk through the entries in L for the max. count.

Of course, you can also keep a maxCount variable s.t. in every merge of L and d you keep this variable the max count s.t. you can avoid the final O(n) scan.