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

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     * 
     * @param n int整型 玩偶数
     * @param m int整型 区间数
     * @param intervals Interval类vector 表示区间
     * @return int整型
     */
    bool check(int n, int m, vector<Interval>& intervals,int x)
    {
        int st=intervals[0].start;
        int res=0;
        for(int i=1;i<n;i++)
        {
            //cout<<st<<endl;
            int t=st+x;
            if(t<=intervals[res].end)
            {
                st=t;
                continue;
            }
            else if(res==m-1)
            {
                return false;
            }
            else
            {
                while(res<m&&t>intervals[res].end)
                {
                    res++;
                }
                if(res==m)
                    return false;
                if(t<intervals[res].start)
                {
                   t=intervals[res].start;
                   st=t;
                }
                else
                {
                   st=t;
                }
            }
        }
        return true;
    }
    static bool cmp(Interval t1, Interval t2)
    {
        return t1.start<t2.start;
    }
    int doll(int n, int m, vector<Interval>& intervals) {
        // write code here
        sort(intervals.begin(),intervals.end(),cmp);
        int l=1,r=n;
        while(r-l>1)
        {
            int mid=(l+r)>>1;
            if(check(n,m,intervals,mid))
            {
                l=mid;
            }
            else
            {
                r=mid;
            }
        }
        return l;
    }
};