https://ac.nowcoder.com/acm/contest/9475/B

牛牛有n(2≤n≤105)(2 \leq n \leq 10^5)(2≤n≤105)个玩偶，牛牛打算把这n个玩偶摆在桌子上，桌子的形状的长条形的，可以看做一维数轴。 桌子上有 M 个互不相交的区间（1≤M≤105）（1≤M≤10^5）（1≤M≤105），这些区间上面可以放玩偶。一个位置只能放一个玩偶，玩偶之间的距离越大越美观，牛牛想最大化 D 的值，其中 D 为最近的两个玩偶之间的距离。请帮牛牛求出 D 的最大可能值。

这个题我在考场上第一反应是贪心，但是没想出来
然后我突然联想到了一个比较相似的题
https://www.luogu.com.cn/problem/P2678
我们二分答案，然后进行判断
然后二分答案是logINT_MAX的
所以只要我们判断的复杂度控制在 n+m 内就可以过掉此题
和那到相似的题几乎一样思路判断
贪心！！！！
区间应该提前按照左或者右端点排序（因为区间不相交，所以排序左端点和右端点都一样）

如果要判断x是否是可行答案
第一个玩偶一定是放在最左边的区间的左端点上
以后放玩偶放在与上一个玩偶相距大于等于x的最左边（贪心思想，尽量往左边放）的可以放置的位置即可

参考代码

/**
 * struct Interval {
 *    long long start;
 *    long long end;
 *    long longerval(long long s, long long e) : start(start), end(e) {}
 * };
 */

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     * 
     * @param n long long整型 玩偶数
     * @param m long long整型 区间数
     * @param long longervals long longerval类vector 表示区间
     * @return long long整型
     */
    struct oppo{
        long long l,r;
        bool operator<(const oppo a)const{
            return l<a.l;
        }
    }h[1000005];
    long long N,M;
    bool check(long long x)
    {
        long long now=0;
        long long i=1;
        long long all=N;
        while(all){
            long long k=max(h[i].l,now);
            now=k+x;
            all--;
            if(all==0) break;
            while(h[i].r<now){
                i++;
                if(i>M)
                    return 0;
            }
        }
        return 1;
    }
    int doll(int n, int m, vector<Interval>& intervals) {
        // write code here
        N=n;
        M=m;
        for(long long i=0;i<m;i++)
        {
            h[i+1].l=intervals[i].start;
            h[i+1].r=intervals[i].end;
        }
        sort(h+1,h+m+1);
        long long l=1,r=INT_MAX,mid;
        int ans=0;
        while(l<=r){
            mid=(l+r)/2;
            if(check(mid)){
                ans=mid;
                l=mid+1;
            }
            else{
                r=mid-1;
            }
        }
        return ans;
    }
};