[C++] - Sorting || Simple and easy || Comprehensive Test Cases and Explanation
IntuitionThe goal is to find the most beautiful item that costs less than or equal to a given price for each query. We need to efficiently determine the maximum
# Intuition
The goal is to find the most beautiful item that costs less than or equal to a given price for each query. We need to efficiently determine the maximum beauty for each query.

# Approach
1. Store Maximum Beauty for Each Price:
    - Use a map to store the maximum beauty for each price. If multiple items have the same price, keep the one with the highest beauty.
2. Sort Prices:
    - Convert the map to a list of pairs and sort it by price. This helps in quickly finding the maximum beauty for any given price.
3. Update Maximum Beauty:
    - Ensure that for each price, the beauty is the maximum possible up to that price. This means if a higher price has a lower beauty, update it to the maximum beauty seen so far.
4. Binary Search for Queries:
    - For each query, use binary search to find the highest price that is less than or equal to the query. Return the corresponding beauty.

# Complexity
- Time Complexity:
    - Building the map takes O(n), where n is the number of items.
    - Sorting the list of prices takes O(nlogn). Each query is processed in O(logn) due to binary search.
    - Overall, the time complexity is O(nlogn+mlogn), where m is the number of queries.

- Space Complexity:
    - The space complexity is O(n) for storing the map and the list of prices.

# Code
```cpp []
// GCC 13.1 (C++ 23)
#include <iostream>
#include <vector>
#include <algorithm>
#include <unordered_map>
#include <cassert>
#include <chrono>

using std::vector;
using std::pair;
using std::unordered_map;
using std::cout;
using std::endl;
using std::chrono::high_resolution_clock;
using std::chrono::duration_cast;
using std::chrono::milliseconds;

class Solution {
public:
    /**
     * @brief Finds the maximum beauty for a given query using binary search.
     * 
     * This function performs a binary search on a sorted vector of pairs to find the maximum beauty
     * value that is less than or equal to the given query.
     * 
     * @param v A sorted vector of pairs where the first element is the price and the second element is the beauty.
     * @param query The query value to find the maximum beauty for.
     * @return The maximum beauty value for the given query.
     */
    int solve(const vector<pair<int, int>>& v, int query) {
        int s = 0, e = v.size() - 1;
        int ans = 0;
        while (s <= e) {
            int mid = s + (e - s) / 2;
            if (v[mid].first <= query) {
                ans = v[mid].second;
                s = mid + 1;
            } else {
                e = mid - 1;
            }
        }
        return ans;
    }

    /**
     * @brief Computes the maximum beauty for each query.
     * 
     * This function processes a list of items and queries to determine the maximum beauty value for each query.
     * It uses a hash map to store the maximum beauty for each price, sorts the items, and then uses binary search
     * to find the maximum beauty for each query.
     * 
     * @param items A vector of vectors where each inner vector contains two integers: price and beauty.
     * @param queries A vector of integers representing the queries.
     * @return A vector of integers representing the maximum beauty for each query.
     */
    vector<int> maximumBeauty(vector<vector<int>>& items, vector<int>& queries) {
        unordered_map<int, int> mp;
        for (const auto& item : items) {
            mp[item[0]] = std::max(mp[item[0]], item[1]);
        }

        vector<pair<int, int>> v(mp.begin(), mp.end());
        std::sort(v.begin(), v.end());

        for (size_t i = 1; i < v.size(); ++i) {
            v[i].second = std::max(v[i - 1].second, v[i].second);
        }

        vector<int> ans;
        ans.reserve(queries.size());
        for (const int query : queries) {
            ans.push_back(solve(v, query));
        }

        return ans;
    }
};

// Unit Test: Basic functionality tests
void testBasicFunctionality() {
    Solution sol;

    // Test case 1
    vector<vector<int>> items1 = {{1, 2}, {3, 2}, {2, 4}, {5, 6}, {3, 5}};
    vector<int> queries1 = {1, 2, 3, 4, 5, 6};
    vector<int> result1 = sol.maximumBeauty(items1, queries1);
    vector<int> expected1 = {2, 4, 5, 5, 6, 6};
    assert(result1 == expected1);  // Expected result: {2, 4, 5, 5, 6, 6}
    cout << "Basic functionality test 1 passed!" << endl;

    // Test case 2
    vector<vector<int>> items2 = {{1, 2}, {1, 2}, {1, 3}, {1, 4}};
    vector<int> queries2 = {1};
    vector<int> result2 = sol.maximumBeauty(items2, queries2);
    vector<int> expected2 = {4};
    assert(result2 == expected2);  // Expected result: {4}
    cout << "Basic functionality test 2 passed!" << endl;

    // Test case 3
    vector<vector<int>> items3 = {{10, 1000}};
    vector<int> queries3 = {5};
    vector<int> result3 = sol.maximumBeauty(items3, queries3);
    vector<int> expected3 = {0};
    assert(result3 == expected3);  // Expected result: {0}
    cout << "Basic functionality test 3 passed!" << endl;
}

// Edge Case: Single element array
void testEdgeCases() {
    Solution sol;

    vector<vector<int>> items4 = {{5, 10}};
    vector<int> queries4 = {5, 10};
    vector<int> result4 = sol.maximumBeauty(items4, queries4);
    vector<int> expected4 = {10, 10};  // Expected result: {10, 10}
    assert(result4 == expected4);
    cout << "Edge case test passed!" << endl;
}

// Stress/Performance Test: Large input array with increasing values
void testPerformance() {
    Solution sol;

    vector<vector<int>> items5;
    for (int i = 1; i <= 1000; ++i) {
        items5.push_back({i, i * 2});
    }
    vector<int> queries5(1000);
    for (int i = 0; i < 1000; ++i) {
        queries5[i] = i + 1;
    }
    auto start = high_resolution_clock::now();
    vector<int> result5 = sol.maximumBeauty(items5, queries5);
    auto end = high_resolution_clock::now();
    auto duration = duration_cast<milliseconds>(end - start).count();
    cout << "Performance test duration: " << duration << " ms" << endl;
    bool performanceTestPassed = true;
    for (int i = 0; i < 1000; ++i) {
        if (result5[i] != (i + 1) * 2) {
            performanceTestPassed = false;
            break;
        }
    }
    assert(performanceTestPassed);  // Expected result: true for all queries
    cout << "Performance test passed!" << endl;
}

// Consistency Test: Run the function multiple times with the same input
void testConsistency() {
    Solution sol;

    vector<vector<int>> items6 = {{4, 9}, {6, 10}, {2, 5}};
    vector<int> queries6 = {4, 6, 2};
    vector<int> firstResult = sol.maximumBeauty(items6, queries6);
    for (int i = 0; i < 10; ++i) {
        vector<int> result = sol.maximumBeauty(items6, queries6);
        assert(result == firstResult);  // Expected result: true for all iterations
    }
    cout << "Consistency test passed!" << endl;
}

// Additional Integration Tests
void testIntegrationCases() {
    Solution sol;

    // Case 1: Already strictly increasing array
    vector<vector<int>> items7 = {{1, 2}, {2, 3}, {3, 4}, {4, 5}, {5, 6}};
    vector<int> queries7 = {1, 2, 3, 4, 5};
    vector<int> result7 = sol.maximumBeauty(items7, queries7);
    vector<int> expected7 = {2, 3, 4, 5, 6};  // Expected result: {2, 3, 4, 5, 6}
    assert(result7 == expected7);
    cout << "Integration test 1 passed!" << endl;

    // Case 2: Array with large gaps
    vector<vector<int>> items8 = {{10, 20}, {20, 30}, {30, 40}, {40, 50}, {50, 60}};
    vector<int> queries8 = {10, 20, 30, 40, 50};
    vector<int> result8 = sol.maximumBeauty(items8, queries8);
    vector<int> expected8 = {20, 30, 40, 50, 60};  // Expected result: {20, 30, 40, 50, 60}
    assert(result8 == expected8);
    cout << "Integration test 2 passed!" << endl;

    // Case 3: Array with no possible item to satisfy the query
    vector<vector<int>> items9 = {{10, 100}, {20, 200}, {30, 300}};
    vector<int> queries9 = {5, 15, 25};
    vector<int> result9 = sol.maximumBeauty(items9, queries9);
    vector<int> expected9 = {0, 100, 200};  // Expected result: {0, 100, 200}
    assert(result9 == expected9);
    cout << "Integration test 3 passed!" << endl;

    // Case 4: Array with multiple items having the same price
    vector<vector<int>> items10 = {{10, 100}, {10, 200}, {10, 300}};
    vector<int> queries10 = {10};
    vector<int> result10 = sol.maximumBeauty(items10, queries10);
    vector<int> expected10 = {300};  // Expected result: {300}
    assert(result10 == expected10);
    cout << "Integration test 4 passed!" << endl;
}

int main() {
    // Running all tests for maximumBeauty
    testBasicFunctionality();  // Basic functionality tests
    testEdgeCases();           // Edge case tests
    testPerformance();         // Performance test
    testConsistency();         // Consistency test
    testIntegrationCases();    // Additional integration tests
    return 0;
}
```
['Array', 'Binary Search', 'Sorting', 'C++']