Problem

Find maximum intervals overlap.

This problem is a classic algorithmic pattern, also known as below.

Meeting Rooms II - Given a list of intervals representing the start and end time of ‘N’ meetings, find the minimum number of rooms required to hold all the meetings.

OR

Interval Scheduling - Given list of jobs as intervals, find minimum number of machines required to run those jobs.

OR

Maximum Elephant Population - There is a number of elephants’ time spans given; here, a time span means the year of birth to the year of death. You have to calculate the period where the maximum number of elephants are alive.

OR

Peak Party Attendance - Consider a big party where a log register for guest’s entry and exit times is maintained. Find the time at which there are maximum guests in the party. Note that entries in the register are not in any order.

OR

Minimum Bus Platforms - At a bus station, you have a time-table for buses’ arrival and departure. You need to find the minimum number of platforms so that all the buses can be accommodated as per their schedule.

OR

Minimum Classrooms Required - Given an array of time intervals (start, end) for classroom lectures (possibly overlapping), find the minimum number of rooms required.

Examples

Example 1:

1
2
3
4
5

Input: intervals = [[0,30],[5,10],[15,20]]
Output: 2
Explanation: We need two meeting rooms
room1: (0,30)
room2: (5,10),(15,20)

Example 2:

1
2
3
4

Input: intervals = [(2,7)]
Output: 1
Explanation: 
Only need one meeting room

More Examples

Example 1 - Guest coming to party

1
2
3
4
5

Input: intervals =[[1,4], [2,5], [9,12], [5,9], [5,12]]
Output: 3
Explanation: First guest in array arrives at 1 and leaves at 4,
second guest arrives at 2 and leaves at 5, and so on.
There are maximum 3 guests at time 5.

Example 2 - Elephant with start and end date of there lives

1
2
3

Input: intervals =[[1990,2013], [1995,2000], [2010,2020], [1992,1999]]
Output: 3
Explanation: There are 3 elephants living in period [1995, 1999].

Example 3 - Number of bus stations or bus station platform

1
2
3
4
5
6
7

Bus Arrival Departure
BusA 0900 hrs 0930 hrs
BusB 0915 hrs 1300 hrs
BusC 1030 hrs 1100 hrs
BusD 1045 hrs 1145 hrs

Output: 3

Example 4 - Number of class rooms required

1
2

class room lectures timings = [(30, 75), (0, 50), (60, 150)]
Output: 2

Solution

Method 1 - Use Count Array

Here is a straightforward approach:

  1. Inspect each time interval to determine the earliest and latest times (when the first and last guest respectively arrive and depart).
  2. Construct an array titled count[] with a length equal to max – min + 1.
  3. Within every interval [x, y], iterate from i = x to y and execute count[i – min]++ for each iteration.
  4. Locate the count array’s largest value and note its index, known as ‘max_index’, then return the sum of max_index + min.

The memory requirement for the aforementioned method is O(max-min+1) and its temporal complexity depends on interval lengths. In the extreme case where every interval stretches from ‘min’ to ‘max,’ the complexity is O((max-min+1)*n), with n as the quantity of intervals.

Method 2 - Using Sorting of Intervals

Here is the pseudocode

  • Split each date range into start date and end date.
  • Sort the dates. If a start date and an end date are the same, put the end date first. For eg. in case of meeting rooms, we will have the meeting room free first, before someone can take it.
  • Start with a count of 0.
  • Iterate through the dates using a sweep-line algorithm:
    • If you get a start date:
      • Increment the count.
      • If the current count is higher than the last best count, set the count, store this start date and set a flag.
    • If you get an end date:
      • If the flag is set, store the stored start date and this end date with the count as the best interval so far.
      • Reset the flag.
      • Decrement the count.

Dry Run

Example: For input of elephant lives: 1990 - 2013 1995 - 2000 2010 - 2020 1992 - 1999

Split and sorted: (S = start, E = end) 1990 S, 1992 S, 1995 S, 1999 E, 2000 E, 2010 S, 2013 E, 2020 E

Iterating through them:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33

count = 0
lastStart = N/A
1990: count = 1
 count = 1 > 0, so set flag
 and lastStart = 1990

1992: count = 2
 count = 2 > 0, so set flag
 and lastStart = 1992

1995: count = 3
 count = 3 > 0, so set flag
 and lastStart = 1995

1999: flag is set, so
 record [lastStart (= 1995), 1999] with a count of 3
 reset flag
 count = 2

2000: flag is not set
 reset flag
 count = 1

2010: count = 2
 since count = 2 < 3, don't set flag

2013: flag is not set
 reset flag
 count = 1

2020: flag is not set
 reset flag
 count = 0

Example 2 -

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

arr[] = {1, 2, 10, 5, 5}
dep[] = {4, 5, 12, 9, 12}

Below are all events sorted by time. Note that in sorting, if two
events have same time, then arrival is preferred over exit.

Time Event Type Total Number of Guests Present
------------------------------------------------------------
1 Arrival 1
2 Arrival 2
4 Exit 1
5 Arrival 2
5 Arrival 3 // Max Guests
5 Exit 2
9 Exit 1
10 Arrival 2
12 Exit 1
12 Exit 0

Time complexity - O(nLogn) time.

What if the number of elephants are very large?

For a (very) large number of elephants, it might be worth skipping the sort. You could create an array indexed by year with +1 for birth, -1 for death. O(e) to fill, and O(n) to sweep, where e is number of elephants and n is date range.

Following is the implementation of above approach. Note that the implementation doesn’t create a single sorted list of all events, rather it individually sorts arr[] and dep[] arrays, and then uses merge process of merge sort to process them together as a single sorted array.

Code

1
2
3
4
5
6
7
8

class Interval {
	public int start;
	public int end;
	public Interval(int start, int end) {
		this.start = start;
		this.end = end;
	}
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35

public int minMeetingRooms(int[][] intervals) {
	int n = intervals.length;
	List<Interval> intervalList = new ArrayList<>(n);
	for (int i = 0; i < n; i++) {
		intervalList.add(new Interval(intervals[i][0], intervals[i][1]));
	}
	return maxOverlapIntervalCount(intervalList);
}

private int maxOverlapIntervalCount(List<Interval> intervals) {

	// break and sort the intervals
	List<Integer> start = intervals.stream().map(i -> i.start).sort();
	List<Integer> end = intervals.stream().map(i -> i.end).sort();


	int maxOverlap = 0;
	int currentOverlap = 0;

	int i = 0;
	int j = 0;
	
	while (i < intervals.size()) {
		if (start[i]<end[j]) {
			currentOverlap++;
			maxOverlap = Math.max(maxOverlap, currentOverlap);
			i++;
		} else {
			currentOverlap--;
			j++;
		}
	}

	return maxOverlap;
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

static class IntervalPoint implements Comparable {
	int timestamp;
	boolean isStart;

	public IntervalPoint(int timestamp, boolean isStart) {
		this.timestamp = timestamp;
		this.isStart = isStart;
	}

	@Override
	public int compareTo(Object o) {
		if (o instanceof Endpoint) {
			IntervalPoint other = (Endpoint) o;
			int result = Integer.compare(timestamp, other.timestamp);
			//in case a result is 0, then one which starts early should be returned
			if (result == 0) {
				return Boolean.compare(((Endpoint) o).isStart, isStart);
			} else {
				return result;
			}
		}
		return 0;
	}
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

public int minMeetingRooms(int[][] intervals) {
	int n = intervals.length;
	List<IntervalPoint> intervalList = new ArrayList<>(n);
	for (int i = 0; i < n; i++) {
		intervalList.add(new IntervalPoint(intervals[i][0], true));
		intervalList.add(new IntervalPoint(intervals[i][1], false));
	}
	return maxOverlapIntervalCount(intervalList);
}

public int maximalOverlapped(List<IntervalPoint> intervalPoints) {
	Collections.sort(intervalPoints);
	int maxOverlap = 0;
	int cur = 0;
	for (IntervalPoint intervalPoint: intervalPoints) {
		if (intervalPoint.isStart) {
			++cur;
			maxOverlap = Math.max(maxOverlap, cur);
		} else {
			--cur;
		}
	}
	return maxOverlap;
}

Complexity

  • ⏰ Time complexity: O(n log n)
  • 🧺 Space complexity: O(1)

Method 3 - Using MinHeap on end times

We can also use minHeap to store the end intervals. We need to keep track of the ending time of all the meetings currently happening so that when we try to schedule a new meeting, we can see what meetings have already ended. We need to put this information in a data structure that can easily give us the smallest ending time. A Min Heap would fit our requirements best.

  1. Sort all the meetings on their start time.
  2. Create a min-heap to store all the active meetings. This min-heap will also be used to find the active meeting with the smallest end time.
  3. Iterate through all the meetings one by one to add them in the min-heap. Let’s say we are trying to schedule the meeting m1.
  4. Since the min-heap contains all the active meetings, so before scheduling meeting m1 we can remove all meetings from the heap that have ended before m1, i.e., remove all meetings from the heap that have an end time smaller than or equal to the start time of m1.
  5. Now add m1 to the heap.
  6. The heap will always have all the overlapping meetings, so we will need rooms for all of them. Keep a counter to remember the maximum size of the heap at any time which will be the minimum number of rooms needed.

Code

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

class Solution {
    public int minMeetingRooms(int[][] intervals) {
        if(intervals == null || intervals.length == 0) {
	        return 0;
	    }
        Arrays.sort(intervals, (a, b) -> Integer.compare(a[0], b[0]));
        PriorityQueue<int[]> minHeap = new PriorityQueue<>((a, b) -> Integer.compare(a[1], b[1]));
        int max = 0;
        for(int[] interval: intervals){
	        while (!minHeap.isEmpty() && minHeap.peek()[1] <= interval[0]) {
				minHeap.poll();
			}
            minHeap.offer(interval);
            max = Math.max(max, minHeap.size());
        }
        return max;
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

public static int minMeetingRooms(List<Interval> intervals) {
	Arrays.sort(intervals, (a, b) -> Integer.compare(a.start, b.start));	// sort intervals by start time
	PriorityQueue<Interval> minHeap = new PriorityQueue<>((a, b) -> Integer.compare(a.end, b.end)); // minHeap by end
	int max = 0;
	for (Interval interval : intervals) {
		while (!minHeap.isEmpty() && minHeap.peek().end <= i.start) {
			minHeap.poll();
		}
		minHeap.offer(interval);
		max = Math.max(max, minHeap.size());
	}
	return max;
}

Complexity

  • ⏰ Time complexity: O(n log n)
  • 🧺 Space complexity: O(n)