牛牛摆玩偶

从左至右对区间进行排序，因为D满足单调性，即如果D可以，D-1一定可以。所以可以在分隔距离D上进行二分答案。
对于固定的D，我们要检查是否可以放置至少N个玩偶。这可以通过贪心的策略来完成。只需将每个玩偶放在最左边的位置即可。一旦奶牛数量达到N，就可以break了，因此可以在O（N + M）时间检查一个D。
所以复杂度为O（（N + M）log（max dist））。

/**
 * struct Interval {
 *    int start;
 *    int end;
 * };
 */
#define LL long long
#define INF 2000000000
#define X start
#define Y end

int nn, mm;
vector<Interval> a;

bool ok(int d) 
{
    LL prev = -1LL * INF * INF;

    int cnt = 0;
    for(int kk = 0; kk < a.size(); kk ++)
    {
        Interval i = a[kk];
        while (max(prev + d, (LL)i.X) <= i.Y) 
        {
            prev = max(prev + d, (LL)i.X);
            cnt++;
            if (cnt >= nn) break;
        }
        if (cnt >= nn) break;
    }

    return (cnt >= nn);
}
bool cmp(Interval x, Interval y)
{
    if(x.X == y.X) return x.Y < y.Y;
    return x.X < y.X;
}


class Solution {
public:
    /**
     * 
     * @param n int整型 玩偶数
     * @param m int整型 区间数
     * @param intervals Interval类vector 表示区间
     * @return int整型
     */
    int doll(int n, int m, vector<Interval>& intervals) {
        // write code here
        sort(intervals.begin(), intervals.end(), cmp);
        a.resize(m);
        nn = n;
         for(int kk = 0; kk < intervals.size(); kk ++) a[kk] = intervals[kk];
        int lo = 1;
        int hi = INF;
        int res = -1;

        while (lo <= hi) 
        {
            int mid = (lo + hi) / 2;
            if (ok(mid)) 
            {
                res = mid;
                lo = mid + 1;
            }
            else 
            {
                hi = mid - 1;
            }
        }
        return res;
    }
};