• Customer Support: admin@thealgorists.com
  • Feedback: We are listening to your every feedback, and taking action to constantly improve your learning experience. If you have any feedback, please use this form: https://thealgorists.com/Feedback.
  • If you are a student, email to admin@thealgorists.com to get special student discount.



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:

  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:



    This is a Premium content. Please subscribe to access the code.
    After subscribing please come back and refresh this page.



    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 beg and end values of intervals


    We keep two sorted arrays: begs and ends.
    begs contains beg 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.


    This is a Premium content. Please subscribe to access the code.
    After subscribing please come back and refresh this page.



    Time Complexity: O(nlogn) for sorting begs + O(nlogn) for sorting ends + O(n) for iterating over begs and ends = O(nlogn)
    Space Complexity: O(n) for two sorted arrays.
    n = total number of given intervals.



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


The above content is written by:

Abhishek Dey

Abhishek Dey

A Visionary Software Engineer With A Mission To Empower Every Person & Every Organization On The Planet To Achieve More

Microsoft | University of Florida

View LinkedIn profile


If you have any feedback, please use this form: https://thealgorists.com/Feedback.




Subscribe to Our Youtube Channel

Follow Us On LinkedIn
wave