Scheduling Problem

The Scheduling Problem is a classic problem in computer science. The goal behind it is to optimize our use of the resources available to us. In this article we'll try to tackle a simple version of said problem.

The Problem:

suppose we our responsible for the scheduling of a group of meeting rooms. Given an array of meeting time intervals intervals where intervals[i] = [starti, endi], return the minimum number of conference rooms required.

Example 1:

Input: intervals = [[0,30],[5,10],[15,20]] 

Output: 2

Meeting room 1 will take meeting [0, 30], while meeting room 2 takes meeting [5, 10] and [15, 20].

Example 2:

Input: intervals = [[7,10],[2,4]] 

Output: 1

The Solution:

At any point of time, we can have multiple rooms that can be occupied. When we have a new meeting that should be affected to a room, we don't necessarily have to know every room that is free. It will be sufficient to find one room.

We will solve this issue by using a Min-Heap that will hold the ending times of every meeting that was already scheduled.

class Solution {
public:
    int minMeetingRooms(vector<vector<int>>& intervals) {
        // min heap, the smallest ending time will be at the top
        priority_queue<int, vector<int>, greater<int>> pq;
        
        // we sort the intervals by starting time 
        sort(intervals.begin(), intervals.end());
        
        for(int i = 0; i < intervals.size(); i++) {
            // if the current starting time is bigger than the top of the min heap
            // the room is free and can be used
            if(pq.size() && intervals[i][0] >= pq.top())
                pq.pop();
            
            pq.push(intervals[i][1]);
        }
        
        return pq.size();
    }
};