Minimum halls required for class scheduling

0 0 9 minutes read

Given N lecture timings, with their start time and end time (both inclusive), the task is to find the minimum number of halls required to hold all the classes such that a single hall can be used for only one lecture at a given time. Note that the maximum end time can be 10⁵.
Examples:

Input: lectures[][] = {{0, 5}, {1, 2}, {1, 10}}
Output: 3
All lectures must be held in different halls because
at time instance 1 all lectures are ongoing.
Input: lectures[][] = {{0, 5}, {1, 2}, {6, 10}}
Output: 2

Approach:

Assuming that time T starts with 0. The task is to find the maximum number of lectures that are ongoing at a particular instance of time. This will give the minimum number of halls required to schedule all the lectures.
To find the number of lectures ongoing at any instance of time. Maintain a prefix_sum[] which will store the number of lectures ongoing at any instance of time t. For any lecture with timings between [s, t], do prefix_sum[s]++ and prefix_sum[t + 1]–.
Afterward, the cumulative sum of this prefix array will give the count of lectures going on at any instance of time.
The maximum value for any time instant t in the array is the minimum number of halls required.

Below is the implementation of the above approach:

C++

// C++ implementation of the approach
#include <bits/stdc++.h>
using namespace std;
 
#define MAX 100001
 
// Function to return the minimum
// number of halls required
int minHalls(int lectures[][2], int n)
{
 
    // Array to store the number of
    // lectures ongoing at time t
    int prefix_sum[MAX] = { 0 };
 
    // For every lecture increment start
    // point s decrement (end point + 1)
    for (int i = 0; i < n; i++) {
        prefix_sum[lectures[i][0]]++;
        prefix_sum[lectures[i][1] + 1]--;
    }
 
    int ans = prefix_sum[0];
 
    // Perform prefix sum and update
    // the ans to maximum
    for (int i = 1; i < MAX; i++) {
        prefix_sum[i] += prefix_sum[i - 1];
        ans = max(ans, prefix_sum[i]);
    }
 
    return ans;
}
 
// Driver code
int main()
{
    int lectures[][2] = { { 0, 5 },
                          { 1, 2 },
                          { 1, 10 } };
    int n = sizeof(lectures) / sizeof(lectures[0]);
 
    cout << minHalls(lectures, n);
 
    return 0;
}

Java

// Java implementation of the approach
import java.util.*;
 
class GFG 
{
static int MAX = 100001;
 
// Function to return the minimum
// number of halls required
static int minHalls(int lectures[][], int n)
{
 
    // Array to store the number of
    // lectures ongoing at time t
    int []prefix_sum = new int[MAX];
 
    // For every lecture increment start
    // point s decrement (end point + 1)
    for (int i = 0; i < n; i++) 
    {
        prefix_sum[lectures[i][0]]++;
        prefix_sum[lectures[i][1] + 1]--;
    }
 
    int ans = prefix_sum[0];
 
    // Perform prefix sum and update
    // the ans to maximum
    for (int i = 1; i < MAX; i++) 
    {
        prefix_sum[i] += prefix_sum[i - 1];
        ans = Math.max(ans, prefix_sum[i]);
    }
    return ans;
}
 
// Driver code
public static void main(String[] args)
{
    int lectures[][] = {{ 0, 5 },
                        { 1, 2 },
                        { 1, 10 }};
    int n = lectures.length;
 
    System.out.println(minHalls(lectures, n));
}
}
 
// This code is contributed by PrinciRaj1992

Python3

# Python3 implementation of the approach 
MAX = 100001
 
# Function to return the minimum 
# number of halls required 
def minHalls(lectures, n) :
 
    # Array to store the number of 
    # lectures ongoing at time t 
    prefix_sum = [0] * MAX;
     
    # For every lecture increment start
    # point s decrement (end point + 1)
    for i in range(n) :
        prefix_sum[lectures[i][0]] += 1;
        prefix_sum[lectures[i][1] + 1] -= 1;
         
    ans = prefix_sum[0];
     
    # Perform prefix sum and update
    # the ans to maximum
    for i in range(1, MAX) :
        prefix_sum[i] += prefix_sum[i - 1];
        ans = max(ans, prefix_sum[i]);
         
    return ans; 
 
# Driver code 
if __name__ == "__main__" : 
 
    lectures = [[ 0, 5 ], 
                [ 1, 2 ], 
                [ 1, 10 ]]; 
                 
    n = len(lectures); 
 
    print(minHalls(lectures, n)); 
 
# This code is contributed by AnkitRai01

C#

// C# implementation of the approach
using System;
     
class GFG 
{
static int MAX = 100001;
 
// Function to return the minimum
// number of halls required
static int minHalls(int [,]lectures, int n)
{
 
    // Array to store the number of
    // lectures ongoing at time t
    int []prefix_sum = new int[MAX];
 
    // For every lecture increment start
    // point s decrement (end point + 1)
    for (int i = 0; i < n; i++) 
    {
        prefix_sum[lectures[i,0]]++;
        prefix_sum[lectures[i,1] + 1]--;
    }
 
    int ans = prefix_sum[0];
 
    // Perform prefix sum and update
    // the ans to maximum
    for (int i = 1; i < MAX; i++) 
    {
        prefix_sum[i] += prefix_sum[i - 1];
        ans = Math.Max(ans, prefix_sum[i]);
    }
    return ans;
}
 
// Driver code
public static void Main(String[] args)
{
    int [,]lectures = {{ 0, 5 },
                       { 1, 2 },
                       { 1, 10 }};
    int n = lectures.GetLength(0);
 
    Console.WriteLine(minHalls(lectures, n));
}
}
 
// This code is contributed by 29AjayKumar

Javascript

<script>
 
// JavaScript implementation of the approach
 
const MAX = 100001;
 
// Function to return the minimum
// number of halls required
function minHalls(lectures, n)
{
 
    // Array to store the number of
    // lectures ongoing at time t
    let prefix_sum = new Uint8Array(MAX);
 
    // For every lecture increment start
    // point s decrement (end point + 1)
    for (let i = 0; i < n; i++) {
        prefix_sum[lectures[i][0]]++;
        prefix_sum[lectures[i][1] + 1]--;
    }
 
    let ans = prefix_sum[0];
 
    // Perform prefix sum and update
    // the ans to maximum
    for (let i = 1; i < MAX; i++) {
        prefix_sum[i] += prefix_sum[i - 1];
        ans = Math.max(ans, prefix_sum[i]);
    }
 
    return ans;
}
 
// Driver code
    let lectures = [ [ 0, 5 ],
                        [ 1, 2 ],
                        [ 1, 10 ] ];
    let n = lectures.length;
 
    document.write(minHalls(lectures, n));
 
 
 
// This code is contributed by Surbhi Tyagi.
 
</script>

Output

Time Complexity: O(MAX)

Auxiliary Space: O(MAX)

where MAX is 100001.

Another Approach:

The above approach works when MAX is limited to 10⁵. When the limits of MAX are extended up to 10⁹, we cannot use above approach due to Memory Limit and Time Limit Constraints.

So, we think in a different dimension, towards sorting and cumulative sum. Store the lecture time (start time and end time) in chronological order, +1 denoting the start time of a lecture and -1 denoting the end time of a lecture. Then apply the concept of cumulative sum, this gives the maximum number of lectures being conducted at a time. This gives the bare minimum number of halls that are required.

Algorithm:

Initialize a vector of pair, Time, the first value of which indicates the entry or exit time of lecture and the second value denotes whether the lecture starts or ends.
Traverse the lectures vector and store the values in the vector Time.
Sort the vector Time.
Maintain two variables answer = 1, and sum = 0. answer denotes the final answer to be returned and sum denotes the number of lectures going on at a particular time. Note that answer is initialized as 1 because at least 1 hall is required for a lecture to be conducted.
Traverse the Time vector, add the second value of the pair into sum and update the answer variable.
Return answer.

Below is the implementation of the above approach:

C++

// C++ implementation of the above approach
#include <bits/stdc++.h>
using namespace std;
 
// Function to return the minimum
// number of halls required
int minHalls(int lectures[][2], int n)
{
 
    // Initialize a vector of pair, Time, first value
    // indicates the time of entry or exit of a lecture
    // second value denotes whether the lecture starts or
    // ends
    vector<pair<int, int> > Time;
 
    // Store the lecture times
    for (int i = 0; i < n; i++) {
        Time.push_back({ lectures[i][0], 1 });
        Time.push_back({ lectures[i][1], -1 });
    }
 
    // Sort the vector
    sort(Time.begin(), Time.end());
 
    int answer = 0, sum = 0;
 
    // Traverse the Time vector and Update sum and answer
    // variables
    for (int i = 0; i < Time.size(); i++) {
        sum += Time[i].second;
        answer = max(answer, sum);
    }
 
    // Return the answer
    return answer;
}
 
// Driver code
int main()
{
    int lectures[][2] = { { 0, 5 }, { 1, 2 }, { 1, 10 } };
    int n = sizeof(lectures) / sizeof(lectures[0]);
 
    cout << minHalls(lectures, n);
 
    return 0;
}
 
// This code is contributed by Shatrunjay Srivastava

Java

// Java implementation of the above approach
import java.util.*;
 
class GFG {
    // Function to return the minimum
    // number of halls required
    static int minHalls(int lectures[][], int n)
    {
 
        // Initialize a vector of pair, Time, first value
        // indicates the time of entry or exit of a lecture
        // second value denotes whether the lecture starts
        // or ends
        ArrayList<pair> Time = new ArrayList<>();
 
        // Store the lecture times
        for (int i = 0; i < n; i++) {
            Time.add(new pair(lectures[i][0], 1));
            Time.add(new pair(lectures[i][1], -1));
        }
 
        // Sort the vector
        Collections.sort(Time, (pair A, pair B) -> {
            return A.first - B.first;
        });
 
        int answer = 0, sum = 0;
 
        // Traverse the Time vector and Update sum and
        // answer variables
        for (int i = 0; i < Time.size(); i++) {
            sum += Time.get(i).second;
            answer = Math.max(answer, sum);
        }
 
        // Return the answer
        return answer;
    }
 
    static class pair {
        int first, second;
        pair(int x, int y)
        {
            first = x;
            second = y;
        }
    }
 
    // Driver Code
    public static void main(String[] args)
    {
        int lectures[][]
            = { { 0, 5 }, { 1, 2 }, { 1, 10 } };
        int n = lectures.length;
 
        System.out.println(minHalls(lectures, n));
    }
}

C#

// C# implementation of the above approach
using System;
using System.Collections.Generic;
 
public class Pair<T, U> {
  public Pair() {}
 
  public Pair(T first, U second)
  {
    this.First = first;
    this.Second = second;
  }
 
  public T First
  {
    get;
    set;
  }
  public U Second
  {
    get;
    set;
  }
};
class GFG {
  public static int cmp(Pair<int, int> a,
                        Pair<int, int> b)
  {
    if(a.First < b.First)
      return -1;
    else
      return 0;
  }
  // Function to return the minimum
  // number of halls required
  static int minHalls(int[, ] lectures, int n)
  {
 
    // Initialize a vector of pair, Time, first value
    // indicates the time of entry or exit of a lecture
    // second value denotes whether the lecture starts
    // or ends
    List<Pair<int, int> > Time
      = new List<Pair<int, int> >();
    // Store the lecture times
    for (int i = 0; i < n; i++) {
      Time.Add(new Pair<int, int>(lectures[i, 0], 1));
      Time.Add(new Pair<int, int>(lectures[i, 1], -1));
    }
 
    // Sort the vector
    Time.Sort(cmp);
 
    int answer = 0, sum = 0;
 
    // Traverse the Time vector and Update sum and
    // answer variables
    for (int i = 0; i < 2*n; i++) {
      sum += Time[i].Second;
      answer = Math.Max(answer, sum);
    }
 
    // Return the answer
    return answer;
  }
 
  // Driver Code
  static public void Main(String[] args)
  {
    int[,] lectures = { { 0, 5 }, { 1, 2 }, { 1, 10 } };
    int n = lectures.GetLength(0);
 
    Console.WriteLine(minHalls(lectures, n));
  }
}
 
// This code is contributed by Abhijeet Kumar(abhijeet19403)

Javascript

// JS implementation of the above approach
 
// Function to return the minimum
// number of halls required
function minHalls(lectures, n) {
    // Initialize a vector of pair, Time, first value
    // indicates the time of entry or exit of a lecture
    // second value denotes whether the lecture starts or
    // ends
    const Time = [];
 
    // Store the lecture times
    for (let i = 0; i < n; i++) {
        Time.push([lectures[i][0], 1]);
        Time.push([lectures[i][1], -1]);
    }
 
    // Sort the vector
    Time.sort((a, b) => a[0] - b[0]);
 
    let answer = 0,
        sum = 0;
 
    // Traverse the Time vector and Update sum and answer
    // variables
    for (let i = 0; i < Time.length; i++) {
        sum += Time[i][1];
        answer = Math.max(answer, sum);
    }
 
    // Return the answer
    return answer;
}
 
// Driver code
const lectures = [
    [0, 5],
    [1, 2],
    [1, 10]
];
const n = lectures.length;
 
console.log(minHalls(lectures, n));
 
// This code is contributed by phasing17

Python3

# Python implementation of the above approach
from typing import List
 
# Function to return the minimum
# number of halls required
def minHalls(lectures: List[List[int]], n: int) -> int:
 
    # Initialize a list of tuples, Time, first value
    # indicates the time of entry or exit of a lecture
    # second value denotes whether the lecture starts
    # or ends
    Time = []
 
    # Store the lecture times
    for i in range(n):
        Time.append((lectures[i][0], 1))
        Time.append((lectures[i][1], -1))
 
    # Sort the list
    Time.sort(key=lambda x: x[0])
 
    answer = 0
    sum = 0
 
    # Traverse the Time list and Update sum and
    # answer variables
    for i in range(len(Time)):
        sum += Time[i][1]
        answer = max(answer, sum)
 
    # Return the answer
    return answer
 
# Driver Code
if __name__ == '__main__':
    lectures = [[0, 5], [1, 2], [1, 10]]
    n = len(lectures)
 
    print(minHalls(lectures, n))

Output

Time Complexity: O(n*log(n))

Auxiliary Space: O(n)

Note that instead of vector of pair, one can use map or priority queue, the time complexity and space complexity would remain the same.

Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 zambiatek!