Hard

# 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)

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:

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).

Code:

Output:
```Minimum number of halls required: 2
```