3281. Maximize Score of Numbers in Ranges || Leetcode Weekly Contest 414 || Explanation || #dsa

Code in comment by one of my slave

[hritikanand]

class Solution {
static bool cmp(const pair<int, int>&a, const pair<int, int>&b){
if(a.second == b.second) return a.first<b.first;
return a.second<b.second;
}
public:
int maxPossibleScore(vector<int>& start, int d) {
int n = start.size();
vector<pair<int, int>> v;
for(int i=0;i<n;i++){
v.push_back({start[i], start[i]+d});
}
sort(v.begin(), v.end(), cmp);
long long l = 0, r = 1e18+7;
long long ans = 0;
auto check = [&](long long mid)->bool{
long long pre = v.back().second;
for(int i=n-2;i>=0;i--){
if(pre - mid < v[i].first) return false;
if(pre - mid > v[i].second) {pre = v[i].second;}
else pre = pre - mid;
}
return true;
};
while(l<=r){
long long mid = l+(r-l)/2;
if(check(mid)) {l = mid+1; ans = mid;}
else r = mid-1;
}
int ans1 =ans;
return ans1;
}
};