-
Notifications
You must be signed in to change notification settings - Fork 0
/
Day_099.cpp
73 lines (66 loc) · 2.6 KB
/
Day_099.cpp
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
/**
*Problem Statement: There is a hallway of length N−1 and you have M
workers to clean the floor. Each worker is responsible for
segment [Li?,Ri?], i.e., the segment starting at Li? and ending
at Ri?. 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?
*Author: Kunal Kathpal (https://github.com/kunal-2002)
*/
#include <bits/stdc++.h>
using namespace std;
int main(){
cout<<"Enter number of test cases:\t";
int T;
cin>>T;
while(T--){
long long n,m;
cin >> n >> m;
vector<pair<long long, long long> > v;
long long li, ri;
for(int i=0; i<m; i++){
cin >> li >> ri;
v.push_back(make_pair(li,ri));
}
sort(v.begin(),v.end());
long long minTime = 1;
long long maxTime = n-1;
long long mid;
long long ans = -1;
while(minTime <= maxTime){
mid = minTime + ((maxTime - minTime) / 2);
long long cur = 1, i = 0;
multiset<long long> e;
while(cur < n){
while(i<m && v[i].first <= cur){
e.insert(v[i].second);
i++;
}
while(!e.empty() && *e.begin() <= cur){
e.erase(e.begin());
}
if(e.empty()){
break;
}
long long x = *e.begin();
e.erase(e.begin());
cur = min(cur+mid,x);
}
if(cur == n){
maxTime = mid - 1;
ans = mid;
}
else {
minTime = mid + 1;
}
}
cout << ans <<"\n";
}
return 0;
}