/*
  Problem 252. Meeting Rooms

  Given an array of meeting time intervals intervals where intervals[i] = [start_i, end_i]
  and start_i < end_i, determine if a person can attend all the meetings without any
  conflicts. Note: Meetings that touch at the endpoint (e.g., [1,2] and [2,3]) do not
  overlap — you can attend both.
  
Constraints: 0 ≤ intervals.length ≤ 10^4, 0 ≤ start_i < end_i ≤ 10^6.
  
Example 1:

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

Example 2:

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


Constraints:
  0 <= intervals.length <= 10^4
  0 <= starti < endi <= 106

  Optimal Solution Walkthrough (O(n log n) time, O(1) extra space if we can modify input):
     1. Sort the intervals by start time.
     2. Iterate through the sorted list and check if any two consecutive meetings overlap:

           if (intervals[i-1][1] > intervals[i][0]) → conflict.

   That's it. Very clean.

   Time Complexity: O(n log n) due to sorting
   Space Complexity: O(1) extra (if sort is in-place) or O(log n) for
       recursion stack in some implementations.
   
 */

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

using namespace std;

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

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

        // 1.Sort the intervals by start time
        ranges::sort(intervals);
        // c++17 sort(intervals.begin(), intervals.end());
        print("sorted", intervals);
        
        int begin = 0, end = 1;        

        // [2,4] [7,0]
        // 2. Iterate through sorted list and check if any two consecutive meetings overlap
        for (int i = 1; i < (int) intervals.size(); i++)
        {
            if (intervals[i-1][end] > intervals[i][begin])
                return false;
        }
        return true;
    }
};

int main(void)
{

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

   for (auto tc: testCases)
    {
        Solution s;
        vector<vector<int>> input = get<0>(tc);
        print("input", input);        
        bool expected = get<1>(tc);
        bool result = s.canAttendMeetings(input);
        EXPECT_EQ(result, expected);
        cout << format("output: {}\n", result); 
        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";
}