In this HackerEarth Customer satisfaction problem solution Alice is the biggest seller in the town who sells notebooks. She has N customers to satisfy. Each customer has three parameters Li, Ri, and Zi denoting the arrival time, departure time, and quantity of notebooks required.

Each customer has to be supplied a total of Zi notebooks between Li and Ri inclusive. What is the minimum rate of W notebooks per unit time by which if Alice produces so that it satisfies the demand of each customer?

Note that Alice does not need to supply Zi to customer i for per unit time but the total of Zi between Li and Ri and distribution does not need to be uniform.


HackerEarth Customer satisfaction problem solution


HackerEarth Customer satisfaction problem solution.

#include<bits/stdc++.h>
using namespace std;
#define FIO ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0)
#define mod 1000000007
#define endl "\n"
#define test ll t; cin>>t; while(t--)
typedef long long int ll;
bool check(vector<pair<ll,ll>>&vp,ll n,ll quan){
    ll ok=true;
    ll ans=vp[0].first*quan;
    for(ll i=0;i<n;i++){
        if(i>0){
            ans+=(vp[i].first-vp[i-1].first)*quan;
        }
        if(ans<vp[i].second){
            ok=false;
        }
        ans-=vp[i].second;
    }
    return ok;
}
int main() {
    FIO;
    test
    {
      ll n,l,r,w; cin>>n;
      vector<pair<ll,ll>>vp;
      for(int i=0;i<n;i++){
          cin>>l>>r>>w;
          vp.push_back({r,w});
      }
      sort(vp.begin(),vp.end());
      for(auto it:vp){
          cout<<it.first<<" "<<it.second<<endl;
      }
      ll st=0,dr=1e18,ans,mid;
      while(st<=dr){
          mid=(st+dr)/2;
          if(check(vp,n,mid)){
              ans=mid;
              dr=mid-1;
          }
          else{
              st=mid+1;
          }
      }
      cout<<ans<<endl;
    }
    return 0;
}

Second solution

MAX = 10000
t = int(input())
while t > 0:
    t -= 1
    n = int(input())
    need = {}
    for i in range(n):
        [l, r, z] = map(int, input().split())
        if r not in need:
            need[r] = 0
        need[r] += z
    ans = 0
    li = list(need.items())
    li.sort()
    cur_need = 0
    for key, val in li:
        cur_need += val
        ans = max(ans, (cur_need + key - 1) // key)
    print(ans)