🙏

জয়  শ্রী  রাম

🕉

---

Here we would try to separate out all overlapping intervals, opposite of what we did in merging overlapping intervals.
A real world scenario where separating out overlapping intervals might be useful is reserving conference rooms for meetings. If we treat meetings as intervals, for any two overlapping meetings we would need a separate conference room.
Let's learn this technique by trying to solve the below problem:

Given a list of meeting time intervals consisting of start and end times, find the minimum number of conference rooms required.

Solution:

• Prerequisite: Fundamentals of Sweep Line Algorithm

1. Sweep Line Algorithm - Min Heap on end value of the Chronologically added intervals:

   
   This is a very simple and intuitive solution. Notice that as the intervals come in chronological order and as we try to process them, what is important to us is to know when is the earliest an already processed interval ends.
   
   If that earliest end time is after the start time of the current interval that means the current interval overlaps with all other previously processed intervals and so separate it out and allocate a new conference room for this meeting. Remember that, all the previously processed intervals have start time less than the start time of the current interval as we are processing the intervals in chronological order. So if the earliest end time is greater than the start time of the current interval then the current interval definitely overlaps with all other intervals already processed and not just with few of them. So we would definitely need a new conference room to accommodate this current interval (meeting) and cannot reuse any of the previously allocated conference rooms.
   
   
   
   On the other hand, if the interval (already processed one) with the earliest end time happens to have the end time less or equal to the start time of the current interval then we can totally reuse the conference room of this interval (meeting) with the earliest end time. Now that we are reusing the conference room do not forget to update the end time (this end time refers to the earliest end time among all the previously proccesed intervals that we were talking about) with the end time of the current interval.
   
   Now let's see how easily we can achieve this using a min heap.
   
   We are using the min heap to track the conference rooms used so far.
   Take a min heap based on the end value of the intervals, which means the interval with the earliest end time will be at the head of the min heap.
   Now if we are adding an interval whose start time is less than the end time time of the interval at head, then add the interval to the min heap as we would need a new conference room for this interval (meeting).
   If the interval we are trying to add has start time greater than the end time of the interval at the head of the heap then we would be able to reuse the conference room where the interval (meeting) at the head of the heap took place. To do this we need to update the end time of the interval at the head of the heap because the nodes in the heap represents the conference rooms being reserved and we need to update the end time to reflect the updated availability of the conference room. This would mean we might need to re-heapify the min heap if this operation changes the minimum end time in the heap. What I mean by this is, the interval with the minimum end time should come to the head of the heap. So, remove the min interval from the heap and add the current interval.
   
   You may be be thinking by now, we do not need to store the intervals in the min heap. We can just store the end values because we are not even using the start values. You are correct. We are going to do exactly that!
   
   

   Implementation:

   
   
   Login to Access Content
   
   
   
   In worst case, all intervals would be overlapping with each other.
   
   

   Time Complexity: O(nlogn) for sorting + O(nlogn) for n times extra-min operation in heap for n elements = O(nlogn)

   extract min operation is O(logn) operation. O(nlogn) because in worst case we do extract-min operation for each of n intervals.
   
   

   Space Complexity: O(n)

   since in worst case when all the intervals are overlapping with each other, ther will be n elements in the heap.
   n = total number of intervals.
   
   

2. Chronological Ordering of beginning and end values of intervals

   
   We keep two sorted arrays: begs[] and ends[].
   begs[] contains beginning or start values for all the intervals in sorted order,
   ends[] contains end values for all the intervals in sorted order.
   Now we will attempt to schedule the meetings in their chronological order.
   The main concept of the algorithm is still similar to the previous one. If the start time is greater than or equal to the earliest end time (available from sorted ends array) then we can reuse the a conference room.
   Otherwise, reserve a new conference room.
   
   

   Implementation:

   
   
   Login to Access Content
   
   
   

Related Must-Read Topics:

1. 1d Range Search
2. Closest Pair
3. Convex Hull
4. Dual Line Sweep & Rectangles Union
5. 2D Intervals Union & Skyline Problem
6. Overlapping 1D Intervals
7. Merging Overlapping 1D Intervals

Instructor: