The straightforward solution is to sort the array and loop through the largest $$$k$$$ elements. This runs in O($$$n\log n$$$) time and uses O($$$n$$$) memory, but it likely won't pass due to the space constraints. Can we do better? Do we really need all the elements, or just the largest $$$k$$$?

We only need the largest $$$k$$$ elements, so we can ignore the smallest $$$n-k$$$. To do this, build a min-heap and keep inserting elements. Once the heap size reaches $$$k+1$$$, use peek to remove the smallest element. Repeat this process until all elements are processed so we end up having the largest $$$k$$$ elements. The space complexity is O($$$k$$$) and the time complexity is O($$$n\log n$$$).

A min-heap is a type of priority queue. However, for this problem, you should build the heap from scratch as instructed. You can use pre-built min-heaps in future solutions.

#include<bits/stdc++.h>
using namespace std;

int n,m,k;

cin >> n >> k;

priority_queue<int,vector<int>, greater<int>> q;

while(n--){
    cin >> m;

    q.push(m);

    if(q.size()>k)q.pop();
}

long long answ = 0;

while(q.size()){
    int c = q.top();q.pop();

    answ += c;
}

cout << answ << '\n';

This is a classic interval scheduling problem, and the solution involves sorting by the second value (ending time). The approach is straightforward:

• Sort the movies by their ending times.

• Start by picking the movie that ends the earliest.

• After picking a movie, skip all movies that overlap with it.

• Keep repeating this process by selecting the next movie that ends the earliest and doesn't overlap with the last chosen movie.

This way, you maximize the number of non-overlapping movies you can select

bool sortbysec(const pair<int,int> &a,const pair<int,int> &b)
{
    if(a.second == b.second){
        return a.first < b.first;
     }
    return (a.second < b.second);
}


int n;

cin >> n;

vector<pair<int,int>> v(n);

int answ = 1,last = 0;

for(int i = 0;i<n;i++) cin >> v[i].first >> v[i].second;

sort(v.begin(),v.end(),sortbysec);

for(int i = 0;i<n;i++){

    if(v[i].f >= v[last].s){
        answ++;last = i;
    }
}


cout << answ << '\n';