Circular Intervals

All submissions for this problem are available.
The integers $0$ to $M  1$ have been arranged in a circular fashion. That is, $0, 1, 2, \ldots, M  1$, are in that order and also, $0$ and $M  1$ are next to each other. The distance between any two adjacent numbers on this circle is 1. You are given $N$ intervals on this, such that no two intervals touch or intersect with each other. The ith interval will be of the form [$L_i, R_i$]. This means that the ith interval contains all the integers between $L_i$ and $R_i$, both end points inclusive. You are supposed to mark exactly one number inside each interval, in such a way that the minimum distance between any two marked numbers is maximized. More formally, we have $0 \leq L_1 \leq R_1 < L_2 \leq R_2 < L_3 \ldots < L_N \leq R_N \leq M  1$. You are supposed to mark exactly $N$ numbers: $A_1, A_2, \ldots, A_N$, such that $L_i \leq A_i \leq R_i$ for all $1 \leq i \leq N$. And you want to do it in such a manner $min_{i \neq j}$ (shortest distance between $A_i$ and $A_j$ ), is maximized. ###Input:  First line of the input contains a pair of integers $M$ and $N$.  The ith of the next $N$ lines contains two numbers $L_i$ and $R_i$ which denote the end points of the ith interval. ###Output:  A single integer denoting the maximized minimum distance between any two marked numbers. ###Constraints  $1 \leq M \leq 10^{18}$  $2 \leq N \leq 4 * 10^5$ ###Subtasks  10 points :  $1 \leq M \leq 10000$  $2 \leq N \leq 100$  25 points :  $1 \leq M \leq 10^{18}$  $2 \leq N \leq 1000$  65 points : No further constraints. ###Sample Input: 9 3 0 2 3 4 5 7 ###Sample Output: 3 ###Explanation: We can choose $A_1 = 0, A_2 = 3, A_3 = 6$. The distance between every adjacent marked pair of numbers is 3, and hence that is the minimum. You can check that you cannot do any better, and hence 3 is the answer.Author:  admin3 
Tags  admin3 
Date Added:  22062018 
Time Limit:  1 sec 
Source Limit:  50000 Bytes 
Languages:  C, CPP14, JAVA, PYTH, PYTH 3.6, PYPY, CS2, PAS fpc, PAS gpc, RUBY, PHP, GO, NODEJS, HASK, rust, SCALA, swift, D, PERL, FORT, WSPC, ADA, CAML, ICK, BF, ASM, CLPS, PRLG, ICON, SCM qobi, PIKE, ST, NICE, LUA, BASH, NEM, LISP sbcl, LISP clisp, SCM guile, JS, ERL, TCL, kotlin, PERL6, TEXT, SCM chicken, PYP3, CLOJ, COB, FS 
Comments
 Please login at the top to post a comment.
SUCCESSFUL SUBMISSIONS
Fetching successful submissions
HELP
If you are still having problems, see a sample solution here. 