CSES - Shared codeLink to this code:
https://cses.fi/paste/bc4c79f7eee4db012401f1/
/*
Set time here:
Start: 2021-06-18 05:22:30
End(when AC):
*/
/*
Author: Shobhit Tewari
*/
#define __STDC_LIMIT_MACROS
#include<iostream>
#include<vector>
#include<set>
#include<map>
#include<unordered_map>
#include<queue>
#include<stack>
#include<cstring>
#include <chrono>
#include<algorithm>
using namespace std;
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
template<class T> using oset = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
#define int long long
#define null 0
#define fio ios_base::sync_with_stdio(false); cin.tie(null);
#define pb push_back
#define sz(v) (int)(v.size())
#define all(v) v.begin(), v.end()
struct custom_hash {
static uint64_t splitmix64(uint64_t x) {
x += 0x9e3779b97f4a7c15;
x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9;
x = (x ^ (x >> 27)) * 0x94d049bb133111eb;
return x ^ (x >> 31);
}
size_t operator()(uint64_t x) const {
static const uint64_t FIXED_RANDOM = chrono::steady_clock::now().time_since_epoch().count();
return splitmix64(x + FIXED_RANDOM);
}
};
template<class T> using PQ = priority_queue<T>;
template<class T> using RPQ = priority_queue<T, vector<T>, greater<T>>;
template<class A, class B> using umap = unordered_map<A, B, custom_hash>;
const int mod = 1e9 +7;
const int infinity = INT64_MAX;
const double pi = 3.1415926535897932384626433832795;
bool comp(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;
}
void solve(){
int n, k;
cin >> n >> k;
vector<pair<int,int>> arr(n);
for(int i=0;i<n;i++) cin >> arr[i].first >> arr[i].second;
sort(all(arr), comp);
if(k>=n) { cout << n << "\n"; return; }
multiset<int> s;
s.insert(arr[0].second);
k--;
int ans = 1;
for(int i=1;i<n;i++) {
auto it = s.upper_bound(arr[i].first);
if(it == s.begin() && k!=0) {
k--;
s.insert(arr[i].second);
ans++;
}
else if(it != s.begin()) {
it--;
s.erase(it);
s.insert(arr[i].second);
ans++;
}
else {
}
}
cout << ans << "\n";
}
signed main(){
fio;
int t=1;
//cin >> t;
while(t--){
solve();
}
return 0;
}