13 months ago

SARTHAK NARANG • 40

#include <iostream>

#include <vector>

#include <queue>

#include <algorithm>

using namespace std;

vector<int> count_cache_items(vector<vector<int>> &data, int a, vector<int> &queries)

{

    // Sort the data by their expiration times (data[i][0] + data[i][1])

    sort(data.begin(), data.end(), [](const vector<int> &a, const vector<int> &b)

         { return a[0] + a[1] < b[0] + b[1]; });

    vector<int> result;

    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> cache; // Min-Heap

    int dataIndex = 0;

    for (int query : queries)

    {

        // Remove expired items from the cache

        while (!cache.empty() && cache.top().first <= query)

        {

            cache.pop();

        }

        // Add items from data to the cache that are still alive at the current query time

        while (dataIndex < data.size() && data[dataIndex][0] <= query)

        {

            cache.push({data[dataIndex][0] + data[dataIndex][1], dataIndex});

            dataIndex++;

        }

        // The number of items in the cache is the size of the priority queue

        result.push_back(cache.size());

    }

    return result;

}

int main()

{

    vector<vector<int>> data = {{105231, 183}, {105334, 34}, {105198, 543}};

    int a = 3;

    vector<int> queries = {105338, 105410};

    vector<int> result = count_cache_items(data, a, queries);

    for (int count : result)

    {

        cout << count << " ";

    }

    return 0;

}