This post is completed by 3 users

Add to List 
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 1Lecture 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 2Example 2
Lecture Timings: [(8, 10), (9, 11), (10, 12), (11, 12)] Minimum Number of Halls Required: 4Example 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 3Solution
First, we will see the O(N^2) solution, and then we will explore an optimized solution with O(N log N).
 Sort the list of lectures based on the start time.
 Create an empty list of halls.
 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.
 The number of halls used is equal to the length of the list of halls.
Time Complexity: O(N^2)
Code:
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:
 Create two separate lists:
startTimes
andendTimes
. These lists will contain the start times and end times of all the lectures, respectively.  Sort both
startTimes
andendTimes
lists individually.  Initialize two pointers,
startPtr
andendPtr
, both pointing to the first element of their respective sorted lists.  Initialize a variable
halls
to keep track of the number of halls required, starting with 0.  Initialize a variable
currentHalls
to keep track of the current number of halls occupied, starting with 0.  Iterate until
startPtr
reaches the end of thestartTimes
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. IncrementcurrentHalls
.  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
andendPtr
to consider the next start and end times.  Update
halls
as the maximum ofhalls
andcurrentHalls
.
 If the current start time (
 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).
Code:
Output:
Minimum number of halls required: 2
Also Read: