Meeting Rooms III

Leetcode question link

Analysis

Basically this is just an Simulation problem.

Note

The most important time complexity optimization is to find out the unused room management could exploit Heap data structure, checkout Room Distribution Order for details

Meeting Distribution Order

Since the startTime is promised to be unique, based on the rule, we know that the distribution should goes from meetings with smaller startTime to larger one. The basic thought is:

1. Sort meetings
2. Distribute meeting to room, counting usage statistics of each room
3. Output most used room

Room Distribution Order

Based on the rules, we know that the room being distributed is always the one with the smallest room number and currently available. Conclude what operations we need for rooms.

Operation	Descriptions
use()	Mark a room used, that room should have the lowest roomIdx among all currently available room
unuse(roomIdx)	Unuse a room by it’s index

Here we introduce two approaches to achieve these.

Array

We use an array bool isUsed[N] to record the status of a room. This require us to iterate the array to find out the lowest unused index, thus has time complexity $O(N)$

Min Heap

We could find Minimum Heap suit this use case really well. We initial a min heap with all unused room index, and:

• use() Remove the index at the heap top
• unuse() Insert the index to the heap

By doing this, we could have $O(\log N)$ time complexity, considering $N$ is the number of room.

Code Implementation

#include <iostream>
#include <numeric>
#include <vector>
#include <format>
#include <algorithm>
#include <queue>
 
using std::cout, std::endl, std::format;
 
using std::vector, std::priority_queue;
 
const bool debug = false;
 
struct TaskInfo
{
    unsigned start = 0;
    unsigned end = 0;
 
    TaskInfo(const vector<int> &vec) : start(vec[0]), end(vec[1]) {}
 
    bool operator<(const TaskInfo &other)
    {
        if (start != other.start)
        {
            return start < other.start;
        }
 
        return end < other.end;
    }
 
    unsigned duration() const
    {
        return end - start;
    }
 
    void delay(unsigned delta)
    {
        start += delta;
        end += delta;
    }
 
    void relocate(unsigned startTime)
    {
        end = startTime + duration();
        start = startTime;
    }
};
 
class MeetingRoomManager
{
private: // private member
    vector<unsigned> mUseCount;
    unsigned tmpMostUsedCount = 0;
    std::priority_queue<unsigned, std::vector<unsigned>, std::greater<unsigned>> tmpUnusedIdxHeap;
 
public: // public member
    // the count of the room
    unsigned mCount = 0;
 
public: // public method
    // initialize manager with room count
    MeetingRoomManager(int count) : mCount(count)
    {
        mUseCount = vector<unsigned>(100);
 
        clear(count);
    }
 
    /**
     * Find a valid room, mark it as used and update the use count.
     * Return index of the used room.
     *
     * Return 100 if room not found.
     */
    unsigned use()
    {
        // room not found
        if (tmpUnusedIdxHeap.empty())
        {
            return 100;
        }
 
        // found room with lowest index
        unsigned unuse = tmpUnusedIdxHeap.top();
        tmpUnusedIdxHeap.pop();
 
        ++mUseCount[unuse]; // update use count
 
        // update most use if needed
        if (mUseCount[unuse] > tmpMostUsedCount)
        {
            tmpMostUsedCount = mUseCount[unuse];
        }
 
        return unuse; // return room idx
    }
 
    /**
     * Unuse a room by its index
     */
    void unuse(unsigned roomIdx)
    {
        tmpUnusedIdxHeap.push(roomIdx);
    }
 
    unsigned mostUsedIdx()
    {
        for (int i = 0; i < mCount; ++i)
        {
            if (mUseCount[i] == tmpMostUsedCount)
            {
                return i;
            }
        }
        return 0;
    }
 
    bool isFull()
    {
        return tmpUnusedIdxHeap.empty();
    }
 
    void clear(unsigned count)
    {
        // reset mCount
        mCount = count;
        // clear most use count
        tmpMostUsedCount = 0;
        // clear use count statistics
        std::fill(mUseCount.begin(), mUseCount.end(), false);
        // init unuse heap
        tmpUnusedIdxHeap = std::priority_queue<unsigned, std::vector<unsigned>, std::greater<unsigned>>();
        for (int i = 0; i < mCount; ++i)
        {
            tmpUnusedIdxHeap.push(i);
        }
    }
};
 
class RoomDistributor
{
 
private: // private classes
    struct FutureReleaseInfo
    {
        unsigned time;
        unsigned roomIdx;
 
        bool operator<(const FutureReleaseInfo &other) const
        {
            if (time != other.time)
            {
                return time > other.time;
            }
            return roomIdx > other.roomIdx;
        }
    };
 
private: // private members
    // manage room usage info
    MeetingRoomManager mManager;
    // record current timestamp
    unsigned mCurTimestamp = 0;
    // record when to release room
    std::priority_queue<FutureReleaseInfo> mReleaseTimeHeap;
 
private: // private methods
    // release one from heap
    // will NOT check empty before action!
    void releaseOne()
    {
        const FutureReleaseInfo &nextReleaseInfo = mReleaseTimeHeap.top();
 
        mManager.unuse(nextReleaseInfo.roomIdx);
        mCurTimestamp = std::max({nextReleaseInfo.time, mCurTimestamp});
        mReleaseTimeHeap.pop();
    }
 
    // release all the room until the given timestamp
    void pushTimeTo(unsigned targetTime)
    {
 
        // already pushed to a time later then given, nothing to do
        if (mCurTimestamp > targetTime)
        {
            return;
        }
 
        // no room is used, just move the time
        if (mReleaseTimeHeap.empty())
        {
            mCurTimestamp = targetTime;
            return;
        }
 
        // release until target time
        while (!mReleaseTimeHeap.empty() && mReleaseTimeHeap.top().time <= targetTime)
        {
            releaseOne();
        }
        mCurTimestamp = targetTime;
    }
 
public:
    RoomDistributor(unsigned roomCount) : mManager(roomCount) {}
 
    // distribute a meeting task to the room
    void distributeTask(const TaskInfo &taskInfo)
    {
        pushTimeTo(taskInfo.start);
 
        // if room still full, push timestamp until next room release
        if (mManager.isFull())
        {
            releaseOne();
        }
 
        // distribute a room
        unsigned roomIdx = mManager.use();
        // record a new future release
        mReleaseTimeHeap.emplace(FutureReleaseInfo(mCurTimestamp + taskInfo.duration(), roomIdx));
    }
 
    /**
     * Release all item that should be released in the future
     */
    void releaseAll()
    {
        while (!mReleaseTimeHeap.empty())
        {
            releaseOne();
        }
    }
 
    unsigned getMostUsedIdx()
    {
        return mManager.mostUsedIdx();
    }
 
    void clear(unsigned count)
    {
        // reset timestamp
        mCurTimestamp = 0;
        // clean heap
        releaseAll();
        // clear mManager
        mManager.clear(count);
    }
};
 
// global variables
unsigned roomCount, meetingCount;
RoomDistributor distributor(0);
vector<TaskInfo> tasks;
 
void initVariables(const vector<vector<int>> &meetings)
{
    // init tasks
    tasks.clear();
    tasks.reserve(meetings.size());
    for (const auto &m : meetings)
    {
        tasks.emplace_back(TaskInfo(m));
    }
    std::sort(tasks.begin(), tasks.end());
 
    // init distributor
    distributor.clear(roomCount);
}
 
void triggerSimulation()
{
    for (const auto &t : tasks)
    {
        distributor.distributeTask(t);
    }
 
    distributor.releaseAll();
}
 
class Solution
{
public:
    int mostBooked(int n, vector<vector<int>> &meetings)
    {
        roomCount = n;
        meetingCount = meetings.size();
 
        initVariables(meetings);
        triggerSimulation();
 
        return distributor.getMostUsedIdx();
    }
};