This post is completed by 3 users

  • 1
 Add to List
Hard

548. Minimum Number of Halls Required for Lecture Scheduling

Given the start time and end time (both inclusive) of each lecture, the task is to determine the minimum number of halls required to accommodate all the classes. The solution ensures that a single hall can only be occupied by one lecture at any given time.

Example 1 
    Lecture Timings: [(9, 10), (10, 11), (11, 12), (9, 12)]
    Minimum Number of Halls Required: 2
    Explanation: In this case, the lectures can be scheduled as follows:
    Hall 1: Lecture 1, Lecture 3
    Hall 2: Lecture 2
Example 2 
    Lecture Timings: [(8, 10), (9, 11), (10, 12), (11, 12)]
    Minimum Number of Halls Required: 4
Example 3 
    Lecture Timings: [(9, 10), (9, 12), (10, 11), (11, 12)]
    Minimum Number of Halls Required: 2
    Explanation: The lectures can be scheduled as follows:
    Hall 1: Lecture 1, Lecture 4
    Hall 2: Lecture 2, Lecture 3
Solution

First, we will see the O(N^2) solution, and then we will explore an optimized solution with O(N log N).

  1. Sort the list of lectures based on the start time.
  2. Create an empty list of halls.
  3. Iterate over each lecture in the sorted list:
    • If there are no halls allocated yet, assign a new hall to the lecture.
    • Otherwise, check each existing hall if it is available during the lecture's time. If an available hall is found, assign the lecture to that hall.
    • If no available hall is found, create a new hall and assign the lecture to it.
  4. The number of halls used is equal to the length of the list of halls.

Time Complexity: O(N^2)

Better Solution:

Yes, we can optimize the algorithm to reduce the time complexity from O(N^2) to O(N log N).

Here's an updated approach that achieves the desired time complexity:

  1. Create two separate lists: startTimes and endTimes. These lists will contain the start times and end times of all the lectures, respectively.
  2. Sort both startTimes and endTimes lists individually.
  3. Initialize two pointers, startPtr and endPtr, both pointing to the first element of their respective sorted lists.
  4. Initialize a variable halls to keep track of the number of halls required, starting with 0.
  5. Initialize a variable currentHalls to keep track of the current number of halls occupied, starting with 0.
  6. Iterate until startPtr reaches the end of the startTimes list:
    • If the current start time (startTimes[startPtr]) is less than the current end time (endTimes[endPtr]), it means a new lecture is starting without any available halls. Increment currentHalls.
      • Increment startPtr to consider the next start time.
    • Otherwise, it means a lecture has ended, and a hall has become available. Decrement currentHalls.
      • Increment both startPtr and endPtr to consider the next start and end times.
    • Update halls as the maximum of halls and currentHalls.
  7. The value of halls will be the minimum number of halls required to hold all the lectures.

With this updated approach, we achieve a more efficient algorithm with a time complexity of O(N log N).

Output: 
Minimum number of halls required: 2

Related Problems: