3 days ago

Shristi Chandrakar • 0

2. Range Selection

bool ok(vector<ll> starts,ll d,ll m){
    ll st=starts[0]+m;
    for(int i=1;i<starts.size();i++){
        st=max(st,starts[i]);
        if(starts[i]+d<st) return false;
        st+=m;
    }
    return true;
}

ll solve(vector<ll> &starts,ll d){
    sort(starts.begin(),starts.end());
    ll l=0,r=1e15;
    while(l<=r){
        ll m=(l+r)/2;
        if(ok(starts,d,m)){
            l=m+1;
        }else r=m-1;
    }
    return r;
}