ENG  RUS Timus Online Judge Online Judge
Problems
Authors
Online contests
Site news
Webboard
Problem set
Submit solution
Judge status
Guide
Register
Authors ranklist
Current contest
Scheduled contests
Past contests
Rules
back to board

Discussion of Problem 1303. Minimal Coverage

greedy works!
Posted by khdz 14 Jan 2022 01:21
I have solved this problem by using an easy greedy algorithm.

MAIN: you need to use an idea of 2 pointers(of course you need to sort array) and take the rightest segment. Left part of segment need to be <= x(another pointer)

The solution below:

void solve() {
int m;
cin >> m;
vector< pair<int, int> > pi;
int a, b;
cin >> a >> b;
while (a || b) {
pi.pb({a, b});
cin >> a >> b;
}
sort(all(pi));
int cnt = 0, j = 0;
vector< pair<int, int> > ans;
j = 0;
int x = 0;
for (; j < sz(pi) && x < m; j++) {
int k = j;
int mx = x;
pair<int, int> par = {-INF, -INF};
while (k < sz(pi) && pi[k].ff <= x) {
if (mx < pi[k].ss) {
mx = pi[k].ss;
par = pi[k];
}
k++;
}
if (par.ff == -INF) {
cout << "No solution\n";
return;
}
x = mx;
ans.pb(par);
if (k > j)
j = k - 1;
}
if (x < m) {
cout << "No solution\n";
return;
}
cout << sz(ans) << '\n';
for (auto &i : ans) {
cout << i.ff << ' ' << i.ss << '\n';
}
}
Re: greedy works!
Posted by hyman00 14 Jan 2022 10:28
always choose segments with rightest right points