Hello all,↵
↵
I am trying to solve CSES movie festival II using the same logic for movie festival I. I am greedily assigning the movies to k people sorted by end times. But this is giving me WA on cases 5, 6, and 7. These cases have n = 200000, so I cannot work them out on paper to find out the problem in my logic. So request to please give me some test cases to help me find the mistake in my logic.↵
↵
My code↵
↵
<spoiler summary="Spoiler">↵
↵
~~~~~↵
#include <bits/stdc++.h>↵
using namespace std;↵
↵
#define int long long↵
↵
int32_t main() {↵
int n, k;↵
cin >> n >> k;↵
↵
vector<pair<int, int>> a(n);↵
for (int i = 0; i < n; ++i) {↵
int x, y;↵
cin >> x >> y;↵
a[i] = {y, x};↵
}↵
↵
sort(a.begin(), a.end());↵
↵
int ans = 0;↵
vector<pair<int, int>> b(k, {0, 0});↵
for (int i = 0; i < n; ++i) {↵
int st = a[i].second;↵
int ed = a[i].first;↵
↵
for (int j = 0; j < k; ++j) {↵
if (b[j].second <= st) {↵
b[j] = {st, ed};↵
++ans;↵
break;↵
}↵
}↵
}↵
↵
cout << ans << endl;↵
}↵
~~~~~↵
↵
</spoiler>↵
↵
↵
I am trying to solve CSES movie festival II using the same logic for movie festival I. I am greedily assigning the movies to k people sorted by end times. But this is giving me WA on cases 5, 6, and 7. These cases have n = 200000, so I cannot work them out on paper to find out the problem in my logic. So request to please give me some test cases to help me find the mistake in my logic.↵
↵
My code↵
↵
<spoiler summary="Spoiler">↵
↵
~~~~~↵
#include <bits/stdc++.h>↵
using namespace std;↵
↵
#define int long long↵
↵
int32_t main() {↵
int n, k;↵
cin >> n >> k;↵
↵
vector<pair<int, int>> a(n);↵
for (int i = 0; i < n; ++i) {↵
int x, y;↵
cin >> x >> y;↵
a[i] = {y, x};↵
}↵
↵
sort(a.begin(), a.end());↵
↵
int ans = 0;↵
vector<pair<int, int>> b(k, {0, 0});↵
for (int i = 0; i < n; ++i) {↵
int st = a[i].second;↵
int ed = a[i].first;↵
↵
for (int j = 0; j < k; ++j) {↵
if (b[j].second <= st) {↵
b[j] = {st, ed};↵
++ans;↵
break;↵
}↵
}↵
}↵
↵
cout << ans << endl;↵
}↵
~~~~~↵
↵
</spoiler>↵
↵
