### EZDUBS's blog

By EZDUBS, history, 4 months ago, Consider this problem: https://www.acwing.com/problem/content/description/129/ Translation: A company has M tasks to be completed. Each task has a corresponding difficulty level and the time required to complete the task. The difficulty level of tasks is $y_i$. The time required to complete the task is $x_i$. If the company completes this task, they will receive $500 x_i+2 y_i$ income. The company has N machines, each with a maximum working time and maximum difficulty level. If the task requires more time than the maximum working time of the machine, the machine cannot complete the task. If the difficulty level of the task exceeds the maximum difficulty level of the machine, the machine cannot complete the next task. Each machine can only complete one task in a day. Each task can only be completed by one machine. Find the maximum number of tasks that can be completed, and the corresponding profit. If there are multiple solutions, choose the one that earns the highest profit.

Input format: For each test case, the first line contains two integers N and M, representing the number of machines and the number of tasks, respectively. Next N rows each contains two integers $x_i$ and $y_i$, respectively representing the maximum working time and maximum difficulty level of each machine. Next M rows each contains two integers $x_i$ and $y_i$, respectively representing the time required to complete the task and the difficulty level of the task.

Solution: The intended solution is greedy. However, my greedy approach does not work:

int n, m;
while (cin >> n >> m) {
// time and level
multiset<pii> machines;
F0R(i,n) {
int a, b; cin >> a >> b;
machines.insert(mp(a,b));
}

F0R(i,m) {
int a, b; cin >> a >> b; tasks[i] = mp(a,b);
}

int cnt = 0, ans = 0;
F0R(i,m) {
while (it != machines.end()) {
cnt++;
machines.erase(it);
break;
}
it++;
}
}
cout << cnt << ' ' << ans << '\n';
}


This fails at the following case: 20 30 42 67 583 0 476 24 1413 58 1079 64 1392 45 274 27 1334 91 120 42 514 36 756 4 1027 53 293 82 166 16 1025 95 1134 26 392 38 432 12 1222 99 1218 94 1363 11 1104 33 406 64 752 11 913 68 1085 44 1005 57 1331 59 90 41 189 78 805 35 606 42 289 6 407 42 558 48 106 5 62 29 1347 50 617 1 1370 48 923 23 1061 54 50 40 650 76 981 8 1116 39 164 23 1221 38 290 82 1345 41 The first number of the answer (i.e. the maximum number of tasks that can be completed) for this case is 16, but my code outputs 15.

The following solution passes:

while(cin >> n >> m){
for(int i = 1; i <= n; i++) cin >> a[i].first >> a[i].second;
for(int i = 1; i <= m; i++) cin >> b[i].first >> b[i].second;

sort(a + 1,a + 1 + n); sort(b + 1,b + 1 + m);

multiset<int> s; s.clear();
long long cnt = 0, ans = 0;
for(int i = m, j = n; i >= 1; i--){
while(j >= 1 && b[i].first <= a[j].first)s.insert(a[j--].second);

multiset<int>::iterator it = s.lower_bound(b[i].second);
if(it != s.end()){
cnt ++;
ans += 500 * b[i].first + 2 * b[i].second;
s.erase(it);
}
}
cout << cnt << " " << ans << endl;
}

//Credits：墨染空


So why does my solution fail but the above solution pass?  Comments (5)
 » Your ans variable can overflow
•  » » the constraints are structured so that it will not overflow.
•  » » » $N,M$ can be $10^5$, $x$ can be $1440$ so the result could be $10^5\cdot500\cdot1440\approx7\cdot10^{10}$. Or is there an explicit sentence in the original statement that forbid this?
•  » » » » Oh I see. But I guess this is not the point because for a small test case like the one I wrote out, it should not overflow anyways. It is probably an algorithmic error, and I can't figure out what it is.
 » Let's forget about the code for a minute and consider the problem conceptually. My greedy is for each task to use the machine with the smallest time out of all machines with a greater time than the task and that has max difficulty level a greater or equal to the task. The greedy of the correct solution is to use the machine with the smallest max difficulty level greater or equal to than the task difficulty level out of all machines with a greater time than the task. Why is my approach wrong and the second approach correct?