牛牛摆玩偶

思路：二分答案，赛中二分少写了一个等号，人傻了

/**
 * struct Interval {
 *    long long start;
 *    long long  end;
 *    Interval(long long s, long long e) : start(start), end(e) {}
 * };
 */
//3 4 1
#define ll long long
bool cmp(Interval& A,Interval& B){
       return A.start<B.start;
}
const ll inf=(1<<31)-1;
class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     * 
     * @param n int整型 玩偶数
     * @param m int整型 区间数
     * @param intervals Interval类vector 表示区间
     * @return int整型
     */
    bool ok(ll d,ll n, ll m, vector<Interval>& intervals){
        ll pre=-inf,cnt=0;
        for(auto &i:intervals){
            while(max(pre+d,1ll*i.start)<=i.end){
                pre=max(pre+d,1ll*i.start);
                cnt++;
                if(cnt>=n) return true;
            }
        }
        return false;
    }
    ll doll(ll n, ll m, vector<Interval>& intervals) {
        // write code here
        ll mi=1,mx=inf,res=-1;
        sort(intervals.begin(),intervals.end(),cmp);
        while(mi<=mx){
            ll mid=(mi+mx)/2;
            if(ok(mid,n,m,intervals)){
                res=mid;
                mi=mid+1;
            }
            else mx=mid-1;
        }
        return res;
    }
};