There is a hallway of length $N-1$ and you have $M$ workers to clean the floor. Each worker is responsible for segment $[L_{i}, R_{i}]$, i.e., the segment starting at $L_{i}$ and ending at $R_{i}$. The segments might overlap. 

Every unit of length of the floor should be cleaned by at least one worker. A worker can clean $1$ unit of length of the floor in $1$ unit of time and can start from any position within their segment. A worker can also choose to move in any direction. However, the flow of each worker should be continuous, i.e, they can’t skip any portion and jump to the next one, though they can change their direction. What’s the minimum amount of time required to clean the floor, if the workers work simultaneously?

------ Input: ------

First line will contain $T$, number of testcases. Then the testcases follow. 
Each testcase contains of $M + 1$ lines of input.
First line contains $2$ space separated integers $N$, $M$, length of the hallway and number of workers.
Each of the next $M$ lines contain $2$ space separated integers $L_{i}$, $R_{i}$, endpoints of the segment under $i^{th}$ worker.

------ Output: ------
For each testcase, output in a single line minimum time required to clean the hallway or $-1$ if it's not possible to clean the entire floor.

------ Constraints  ------
$1 ≤ T ≤ 10^{5}$
$2 ≤ N ≤ 10^{9}$
$1 ≤ M ≤ 10^{5}$
$1 ≤ L_{i} < R_{i} ≤ N$
The sum of $M$ over all tests is atmost $2*10^{5}$

----- Sample Input 1 ------ 
3

10 3

1 10

1 5

6 10

10 1

2 10

10 2

5 10

1 5
----- Sample Output 1 ------ 
3

-1

5
----- explanation 1 ------ 
Case $1$: The first worker cleans the segment $[4, 7]$, the second cleans $[1, 4]$ and the third cleans $[7, 10]$ each taking $3$ units of time. So the minimum time required is $3$ units.

Case $2$: Segment $[1, 2]$ is not covered by any worker and hence the entire hallway can't be cleaned.

Case $3$: The first worker cleans the segment $[5, 10]$ taking $5$ units of time, and the second cleans $[1, 5]$ taking $4$ units of time. So the minimum time required is $max(5, 4) = 5$ units.

Source: codechef | Difficulty: VERY_HARD
Tags: Sorting

Data structures

Mathematics

Complete search


Solutions:
for _ in range(int(input())):
	(n, m) = map(int, input().split())
	v = []
	for _m in range(m):
		(x, y) = map(int, input().split())
		v.append([y, x])
	v.sort()
	l = 0
	r = n - 1
	cnt = -1
	while l <= r:
		mid = (l + r) // 2
		seg = 1
		for i in range(m):
			if seg >= v[i][0] or v[i][1] > seg:
				continue
			else:
				seg = min(seg + mid, v[i][0])
		if seg == n:
			cnt = mid
			r = mid - 1
		else:
			l = mid + 1
	print(cnt)


t1 = int(input())
for i in range(t1):
	(n1, m1) = map(int, input().split())
	v1 = []
	for _m1 in range(m1):
		(x1, y1) = map(int, input().split())
		v1.append([y1, x1])
	v1.sort()
	l1 = 0
	r1 = n1 - 1
	ct = -1
	while l1 <= r1:
		mid = (l1 + r1) // 2
		seg = 1
		for i in range(m1):
			if seg >= v1[i][0] or v1[i][1] > seg:
				continue
			else:
				seg = min(seg + mid, v1[i][0])
		if seg == n1:
			ct = mid
			r1 = mid - 1
		else:
			l1 = mid + 1
	print(ct)


t2 = int(input())
for i in range(t2):
	(n2, m2) = map(int, input().split())
	v2 = []
	for _m2 in range(m2):
		(x2, y2) = map(int, input().split())
		v2.append([y2, x2])
	v2.sort()
	l2 = 0
	r2 = n2 - 1
	ct = -1
	while l2 <= r2:
		mid = (l2 + r2) // 2
		seg = 1
		for i in range(m2):
			if seg >= v2[i][0] or v2[i][1] > seg:
				continue
			else:
				seg = min(seg + mid, v2[i][0])
		if seg == n2:
			ct = mid
			r2 = mid - 1
		else:
			l2 = mid + 1
	print(ct)


t = int(input())
for i in range(t):
	(p, q) = map(int, input().split())
	v = []
	for _q in range(q):
		(x, y) = map(int, input().split())
		v.append([y, x])
	v.sort()
	l = 0
	r = p - 1
	cnt = -1
	while l <= r:
		mid = (l + r) // 2
		seg = 1
		for i in range(q):
			if seg >= v[i][0] or v[i][1] > seg:
				continue
			else:
				seg = min(seg + mid, v[i][0])
		if seg == p:
			cnt = mid
			r = mid - 1
		else:
			l = mid + 1
	print(cnt)