**Heap Sort**

$$$Important$$$ $$$Note$$$: in this problem k is small as it is the min(n,1000). We should take advantage of this fact to solve the problem in an efficient way.

**Solution Using Sorting**

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$$$?

**Solution Using Heap Sort**

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$$$).

**Important**

Don't create an array of size $$$n$$$ to process the input. Store the values directly in a single integer to avoid the space complexity becoming O($$$n$$$).

**Code**

**Solution Using Priority Queue**

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.

**Code**

#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';

**You Know Who**

Hermione is busy now, So we need an efficient solution!

**Solution**

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

**Code**

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';

Auto comment: topic has been updated by Adam_Jardali (previous revision, new revision, compare).Auto comment: topic has been updated by Adam_Jardali (previous revision, new revision, compare).