/*
  LeetCode 253. Meeting Rooms II – Minimum Number of Conference Rooms Required

  Now, given the same intervals, return the minimum number of conference rooms required so that no
  two meetings are in the same room at the same time.

  Approach A: Min-Heap (Priority Queue) of End Times (most common in interviews)
    * Sort intervals by start time.
    * Use a min-heap to keep track of the end times of meetings currently happening.
    * For each new meeting:
      * If the earliest-ending meeting has already finished (heap.top() <= current.start), reuse that room (pop).
      * Else, need a new room.
    * Always push the current meeting's end time.

  Track the maximum size of the heap at any time → that's the answer.

  Approach B: Two Pointers / Sweep Line (also very popular)  
    * Create two arrays: all start times and all end times.
    * Sort both.
    * Use two pointers: increment room count on start, decrement on end.
    * Track current and max rooms.

  This version often runs slightly faster in practice.
  
  Which one to code first? The heap version is more intuitive and directly shows room allocation.  
 */

#include <bits/stdc++.h>
#include <gtest/gtest.h>

using namespace std;

void print(const string&, vector<vector<int>>&);

class Solution_minHeap {
public:
    int minMeetingRooms(vector<vector<int>>& intervals)
    {
        // What if the array is empty or has one meeting?
        if (intervals[0].empty()) return 0;
        if (intervals.size() == 1) return 1;

        // sort intervals
        sort(intervals.begin(), intervals.end());
        print("sort", intervals);

        // min heap to track end times of meetings
        priority_queue<int, vector<int>, greater<int>> pq;

        int maxRooms = 0;

        for (const auto& interval: intervals)
        {
            int beginTime = interval[0];
            int endTime = interval[1];

            while (!pq.empty() && beginTime >= pq.top() /* end time */)
            {
                pq.pop();
            }

            pq.push(endTime);

            //--------------------------------
            // Debug
            vector<int> tmp;
            while (!pq.empty())
            {
                tmp.push_back(pq.top());
                pq.pop();
            }
            cout << "endTimes: ";
            for (auto& i: tmp) cout << i << " ";
            cout << endl;
            for (auto& i: tmp) pq.push(i);
            //--------------------------------

            maxRooms = max(maxRooms, (int)pq.size());
        }

        return maxRooms;
    }

public:
};

int main(void)
{

    vector<tuple<vector<vector<int>>, int>> testCases = {
        //  input
        {  { {15,20},{5,10},{0,30}   }, 2  },
        {  { {7,10},{2,4}            }, 1  },
        {  { {1,2},{2,3}             }, 1  },
        {  { {}                      }, 0  },
        {  { {1,7},{2,5},{3,6},{7,8} }, 3  },
    };

   for (auto tc: testCases)
    {
        Solution_minHeap s;
        vector<vector<int>> input = get<0>(tc);
        print("input", input);
        int expected = get<1>(tc);
        int result = s.minMeetingRooms(input);
        cout << format("numRooms: {}\n", result);
        EXPECT_EQ(result, expected);
        cout << "--------------------------------\n";
    }

   return 0;
}

void print(const string& label, vector<vector<int>>& v)
{
    cout << label <<": [";
    for (size_t i = 0; i < v.size(); i++)
    {
        cout << "[";
        for (size_t j = 0; j < v.at(i).size(); j++)
        {
            cout << v.at(i).at(j) << (j == 0 ? "," : "");
        }
        cout << (i == v.size() - 1 ? "]" : "],");
    }
    cout << "]\n";
}