INOI1201 | Editorial by salil03

All Editorials
 
**Problem in short**: 
There are N people, and person i takes a[i], b[i] and c[i] time to do task a, b, c respectively. Only one person can do task a at a given point of time, and each person must do tasks a, b, c in-order. In which order should the N people do task a, so as to minimize the time at which everyone is done with all of their tasks. N <= 2 * 10^5.
​
**Editorial**
Can you solve the problem for just 2 players. Player 1 and Player 2?
Can you come up with a criteria for player i to go before player j, or vice versa. An expression involving a[i], d[i], a[j], d[j] based on which you know whether i should go before or after j.?
Use the above criteria as the comparison function for sorting all the players. Make sure you understand why its valid to use the above criteria as a comparison function.
You know the order in which the players will do task a. So **simply calculate the time at which each person finishes task c and output the maximum.**
​
Example code:https://www.codechef.com/viewsolution/20225458
```
#include <bits/stdc++.h>
using namespace std;
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int n;
    cin >> n;
    vector<pair<int, int>> people;
    int x, y, z;
    for (int i = 0; i < n; i++)
    {
        cin >> x >> y >> z;
        people.push_back(make_pair(y + z, x));
    }
    sort(people.begin(), people.end());
    int total = people[0].first, total1 = people[n - 1].first + people[n - 1].second;
    for (int i = 0; i < n; i++)
    {
        total += people[i].second;
    }
    cout << max(total, total1);
    return 0;
}
```
​

Problem in short:
There are N people, and person i takes a[i], b[i] and c[i] time to do task a, b, c respectively. Only one person can do task a at a given point of time, and each person must do tasks a, b, c in-order. In which order should the N people do task a, so as to minimize the time at which everyone is done with all of their tasks. N <= 2 * 10^5.

Editorial
Can you solve the problem for just 2 players. Player 1 and Player 2?
Can you come up with a criteria for player i to go before player j, or vice versa. An expression involving a[i], d[i], a[j], d[j] based on which you know whether i should go before or after j.?
Use the above criteria as the comparison function for sorting all the players. Make sure you understand why its valid to use the above criteria as a comparison function.
You know the order in which the players will do task a. So simply calculate the time at which each person finishes task c and output the maximum.

Example code:https://www.codechef.com/viewsolution/20225458

#include <bits/stdc++.h>
using namespace std;
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int n;
    cin >> n;
    vector<pair<int, int>> people;
    int x, y, z;
    for (int i = 0; i < n; i++)
    {
        cin >> x >> y >> z;
        people.push_back(make_pair(y + z, x));
    }
    sort(people.begin(), people.end());
    int total = people[0].first, total1 = people[n - 1].first + people[n - 1].second;
    for (int i = 0; i < n; i++)
    {
        total += people[i].second;
    }
    cout << max(total, total1);
    return 0;
}