algorithm - How to find the minimum value of M? -

i'm trying solve problem:

you have n relatives. talk ith relative ti minutes. each minute costs 1 dollar . after conversation, add recharge of xi dollars in mobile. initially, have m dollars balance in mobile phone.

find minimum value of m, must have initially, in phone, don't run out of balance during of call (encounter negative balance).

note : can call relatives in order. each relative called once.

input:

n t1  x1 t2  x2  2 1 1  2 1 

output:

2 

this looks easy me @ first i'm not able find exact solution.

my initial thoughts:

we have no problem xi > ti not reduce our initial balance. need take care of situation where run loss i.e ti > xi. unable make expression result in minimum initial value.

need guidance in approaching problem find optimal solution.

update:-

binary search approach seems lead wrong result (as proved test case provided in comment below user greybeard.

so, approach.we maintain difference between call cost , recharge amount.

then maintain 2 arrays/vectors. if our recharge amount strictly greater cost of call, put call in first array ,else put in second array.

then can sort first array according cost , second array according recharge amount. update diff adding least amount of recharge call our cost greater recharge

then can iterate through our first array , update our max requirement,requirement each call , current balance.finally, our answer maximum between max requirement , diff have maintained.

example :-

   n = 2    t1 = 1 r1 = 1    t2 = 2 r2 = 1 

our first array contains nothing calls have cost greater or equal recharge amount. so, place both calls in our second array diff gets updated 2 before sort array. then, add min recharge can calls our diff(i.e 1).now, diff stands @ 3.then our first array contains no elements, our answer equal diff i.e 3.

time complexity :- o(nlogn)

working example:-

#include<bits/stdc++.h> using namespace std; #define maxn 100007  int n,diff; vector<pair<int,int> > v1,v2;  int main(){     diff = 0;     cin>>n;     for(int i=0;i<n;i++){     int cost,recharge;     cin>>cost>>recharge;     if(recharge > cost){        v1.push_back(make_pair(cost,recharge));     }else{        v2.push_back(make_pair(recharge,cost));     }     diff += (cost-recharge);    }    sort(v1.begin(), v1.end());    sort(v2.begin(), v2.end());    if(v2.size() > 0)diff += v2[0].first;    int max_req = diff, req = 0,cur = 0;    for(int i=0; i<v1.size(); i++){       req = v1[i].first - cur;       max_req = max(max_req, req);       cur += v1[i].second-v1[i].first;    }    cout<<max(max_req,diff)<<endl;    return 0; }