#include <iostream>
#include <vector>
#include <unordered_map>

using namespace std;

struct timeRange {
    int start;
    int end;
    string room;
};

class Calendar {
    private:
        vector<string> rooms;
        vector<timeRange> meetings;

    public:
        Calendar(vector<string> rooms) {
            this->rooms = rooms;
            meetings = {};
        }

        string scheduleMeetings(vector<int> range) {
            // O(n)
            // room vs possiblity
            unordered_map<string, bool> possbile_rooms;
            // room vs unavailabity map
            unordered_map<string, bool> unavail_rooms;
            for (auto meeting : meetings) {
                if (range[1] <= meeting.start || meeting.end<=range[0]) {
                    // non-overlap
                    possbile_rooms[meeting.room] = true;
                } else {
                    // overlap
                    possbile_rooms[meeting.room] = false;
                }
                unavail_rooms[meeting.room] = true;
            }
            // check existing rooms
            for (auto it : possbile_rooms) {
                if (it.second == true) {
                    meetings.push_back({range[0], range[1], it.first});
                    return it.first;
                }
            }
            // check new rooms
            for (auto room : rooms) {
                if (unavail_rooms.find(room) == unavail_rooms.end()) {
                    meetings.push_back({range[0], range[1], room});
                    return room;
                }
            }
            cout << "No conference room can be alloted";
            return "";
        }
};

int main() {
    Calendar* c = new Calendar({"a", "b", "c"});
    // vector<vector<int>> ranges = {{1, 4}, {3, 5}, { 3, 9}, {5, 6}};
    // vector<vector<int>> ranges = {{1, 3}, {3, 5}, { 5, 7}, {5, 6}};
    vector<vector<int>> ranges = {{1, 4}, {3, 5}, { 3, 9}, {1,4}, {5, 6}};
    for (int i=0; i<ranges.size(); i++) {
        cout << c->scheduleMeetings(ranges[i]) << endl;
    }
    return 0;
}