Maximum Number of Overlapping Intervals

Question

this question came in my onsite Amazon interview. Can someone come up with an optimizated solution? What data structure would you use to store the sessions?

Given the start and end time of a session, find the maximum number of sessions that were active at the same time.

Example:

ID. Start Time , End Time

1. 1 , 4

2. 3 , 5

3. 2 , 7

4. 5 , 10

Answer: 3

I was able to come up with a brute-force solution. I stored the sessions in list of lists [[s1,e1],[s2,e2]]. I ran a loop for each unit of time through each session in the list and calculated the maximum number of overlaps. Obviously, this is not efficient. What can I use for a more efficient solution? Would it be better to store the start and end times in two different arrays?

Answer 1

I have solved this problem using an unordered map and cumulative sum in O(n) time. My solution:

int maxSession( vector<vector<int>>meeting ){
    int sz = meeting.size();
    unordered_map<int, int> umap;
    int lastMeetingEnd = meeting[0][1];
    for(int i = 0; i < sz; i++){
        umap[meeting[i][0]] += 1;
        umap[meeting[i][1]] += -1;
        lastMeetingEnd = max(lastMeetingEnd, meeting[i][1]);
    }

    int sum = umap[0];
    int ans = sum;
    for(int i = 1; i <= lastMeetingEnd; i++){
        sum += umap[i];
        if(sum > ans)
            ans = sum;
    }
    return ans;
}

Input: {{1,4},{3,5},{2,7},{5,10}}
Output: 3

Input: {{1, 5}, {2, 3}, {3, 10}, {4,9}, {7,10},{6,11}}
Output: 4

Answer 2

Convert the input to pairs of time, and a number which I will call "delta". That delta will be 1 or -1 depending on whether the time is a start time or end time. It indicates whether chronologically a session is added, or removed from the set of ongoing sessions.

Sort that array by time and when tied, by the delta.

Now traverse that sorted array and keep a running sum of delta. The maximum value that running sum reaches during that traversal is the answer.

Note: if the domain of the time dimension is integer, and the range is rather small, then counting sort can be used to improve on the time complexity.