Cleaning Drive solution – There is a hallway of length N−1N−1 and you have MM workers to clean the floor

Cleaning Drive solution

Cleaning Drive solution

There is a hallway of length N1N−1 and you have MM workers to clean the floor. Each worker is responsible for segment [Li,Ri][Li,Ri], i.e., the segment starting at LiLi and ending at RiRi. The segments might overlap.

Every unit of length of the floor should be cleaned by at least one worker. A worker can clean 11 unit of length of the floor in 11 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: Cleaning Drive solution

  • First line will contain TT, number of testcases. Then the testcases follow.
  • Each testcase contains of M+1M+1 lines of input.
  • First line contains 22 space separated integers NNMM, length of the hallway and number of workers.
  • Each of the next MM lines contain 22 space separated integers LiLiRiRi, endpoints of the segment under ithith worker.

Output: Cleaning Drive solution

For each testcase, output in a single line minimum time required to clean the hallway or 1−1 if it’s not possible to clean the entire floor.

Constraints : Cleaning Drive solution

  • 1T1051≤T≤105
  • 2N1092≤N≤109
  • 1M1051≤M≤105
  • 1Li<RiN1≤Li<Ri≤N
  • The sum of MM over all tests is atmost 21052∗105

Sample Input: Cleaning Drive solution

3
10 3
1 10
1 5
6 10
10 1
2 10
10 2
5 10
1 5

Sample Output: Cleaning Drive solution

3
-1
5

Cleaning Drive solution

Explanation: Cleaning Drive solution

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

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

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

Cleaning Drive solution

Program Code: Cleaning Drive solution

C++

#pragma GCC optimize("Ofast") 
#pragma GCC target("avx,avx2,fma") 
#pragma GCC optimization ("unroll-loops")
#include <bits/stdc++.h>
#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
#define fast ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
template<class T>
using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
// find_by_order(k) returns iterator to kth element starting from 0
// order_of_key(k) returns count of elements strictly smaller than k
#define fix(f,n) std::fixed<<std::setprecision(n)<<f
#define epsi (double)(0.00000000001)
typedef long long int ll;
typedef unsigned long long int ull;
#define vi vector<ll>
#define pii pair<ll,ll>
#define vii vector<pii>
#define max(a,b) ((a>b)?a:b)
#define min(a,b) ((a>b)?b:a)
#define min3(a,b,c) min(min(a,b),c)
#define max3(a,b,c) max(max(a,b),c)
#define ff(a,b,c) for(int a=b; a<=c; a++)
#define frev(a,b,c) for(int a=c; a>=b; a--)
#define REP(a,b,c) for(int a=b; a<c; a++)
#define pb push_back
#define mp make_pair
#define endl "\n"
#define all(v) v.begin(),v.end()
#define sz(a) (ll)a.size()
#define F first
#define S second
#define ld long double
//#define INF 2000000000000000000
#define mem0(a) memset(a,0,sizeof(a))
#define mem1(a) memset(a,-1,sizeof(a))
#define ub upper_bound
#define lb lower_bound
#define setbits(x) __builtin_popcountll(x)
#define trav(a,x) for(auto &a:x)
#define make_unique(v) v.erase(unique(v.begin(), v.end()), v.end())
#define rev(arr) reverse(all(arr))
#define gcd(a,b) __gcd(a,b);
#define ub upper_bound // '>'
#define lb lower_bound // '>='
#define qi queue<ll>
#define si stack<ll>

const long double PI = acos(-1);

mt19937_64 rang(chrono::high_resolution_clock::now().time_since_epoch().count());
int rng(int lim) {
uniform_int_distribution<int> uid(0,lim-1);
return uid(rang);
}

bool prime[200001];
void SieveOfEratosthenes(){ 
memset(prime, true, sizeof(prime)); 
prime[1]=false;
for(ll p=2; p*p<=200000; p++){
if(prime[p] == true){
for (int i=p*p; i<=200000; i += p)
prime[i] = false;
}
}
return;
}

ll gcdExtended(ll a, ll b, ll *x, ll *y){
if(a == 0){
*x = 0;
*y = 1;
return b;
}
ll x1, y1;
ll gcd = gcdExtended(b%a, a, &x1, &y1);
*x = y1 - (b/a) * x1;
*y = x1;
return gcd;
}

ll modInverse(ll a, ll m){
ll x, y;
ll g = gcdExtended(a, m, &x, &y);
ll res = (x%m + m) % m;
return res;
}

ll binary_Search(vector<ll>&arr,ll key){
ll l=0,r=arr.size()-1;
ll ans;
while(l<=r){
ll mid=(l+r)/2;
ll value=arr[mid];
if(value>key){
r=mid-1;
}else if(value==key){
return mid;
}else{
l=mid+1;
}
}
return -1;
}

ll power(ll x,ll y,ll p){
ll res = 1;
x = x % p;
if (x == 0) return 0;
while (y > 0){ 
if (y & 1) 
res = (res*x) % p;
y = y>>1;
x = (x*x) % p;
}
return res;
}

const int N=1e5+5;
const ll INF=1e18;

void solve(){
ll n,m;
cin >> n >> m;
vii v(m);
for(int i=0 ; i<m ; i++){
cin >> v[i].S >> v[i].F;
}
sort(all(v));
ll l=1,r=n,mid,ans=-1;
while(l<=r){
mid=(l+r)/2;
int cur=1;
bool ok=1;
for(int i=0 ; i<m ; i++){
if(cur>=v[i].F || cur<v[i].S) continue;
cur=min(v[i].F,cur+mid);
}
if(cur==n && ok){
ans=mid;
r=mid-1;
}else{
l=mid+1;
}
}
cout << ans << endl;
}

int main(){
fast;
//freopen ("auxiliary.in","r",stdin);
//freopen ("auxiliary.out","w",stdout);
int test=1;
cin >> test;
while(test--){
solve();
}
return 0;
}

JAVA

import java.io.OutputStream;
import java.io.IOException;
import java.io.InputStream;
import java.io.PrintWriter;
import java.io.PrintStream;
import java.util.Arrays;
import java.util.PriorityQueue;
import java.util.AbstractCollection;
import java.io.InputStream;

/**
* Built using CHelper plug-in
* Actual solution is at the top
*
* @author sarthakmanna
*/
public class Main {
public static void main(String[] args) {
InputStream inputStream = System.in;
OutputStream outputStream = System.out;
FastReader in = new FastReader(inputStream);
PrintWriter out = new PrintWriter(outputStream);
CleaningDrive solver = new CleaningDrive();
int testCount = Integer.parseInt(in.next());
for (int i = 1; i <= testCount; i++)
solver.solve(i, in, out);
out.close();
}

static class CleaningDrive {
long N;
int M;
long[][] W;

public void solve(int testNumber, FastReader in, PrintWriter out) {
int i, j, k;

N = in.nextLong();
M = in.nextInt();
W = new long[M][];
for (i = 0; i < M; ++i) W[i] = new long[]{in.nextLong(), in.nextLong() - 1};
Arrays.sort(W, (a, b) -> a[0] == b[0] ? Long.compare(a[1], b[1]) : Long.compare(a[0], b[0]));

final long INF = Long.MAX_VALUE >> 1;
long l = 0, r = INF;
while (true) {
long mid = l + r >> 1;
if (l == mid) {
if (canWipe(l)) out.println(l);
else if (canWipe(r)) out.println(r);
else out.println(-1);
return;
} else if (canWipe(mid)) {
r = mid;
} else {
l = mid + 1;
}
}
}

boolean canWipe(long time) {
long l = 1;
int k = 0;
PriorityQueue<Long> pq = new PriorityQueue<>();
do {
while (k < M && W[k][0] <= l) {
pq.add(W[k++][1]);
}
while (!pq.isEmpty() && pq.peek() < l) pq.poll();
if (pq.isEmpty()) break;

long top = pq.poll();
long d = Math.min(time, top - l + 1);
l += d;
} while (true);

return l >= N;
}

}

static class FastReader {
static final int BUFSIZE = 1 << 20;
static byte[] buf;
static int index;
static int total;
static InputStream in;

public FastReader(InputStream is) {
try {
in = is;
buf = new byte[BUFSIZE];
} catch (Exception e) {
}
}

private int scan() {
try {
if (index >= total) {
index = 0;
total = in.read(buf);
if (total <= 0)
return -1;
}
return buf[index++];
} catch (Exception | Error e) {
System.err.println(e.getMessage());
return 13 / 0;
}
}

public String next() {
int c;
for (c = scan(); c <= 32; c = scan()) ;
StringBuilder sb = new StringBuilder();
for (; c > 32; c = scan())
sb.append((char) c);
return sb.toString();
}

public int nextInt() {
int c, val = 0;
for (c = scan(); c <= 32; c = scan()) ;
boolean neg = c == '-';
if (c == '-' || c == '+')
c = scan();
for (; c >= '0' && c <= '9'; c = scan())
val = (val << 3) + (val << 1) + (c & 15);
return neg ? -val : val;
}

public long nextLong() {
int c;
long val = 0;
for (c = scan(); c <= 32; c = scan()) ;
boolean neg = c == '-';
if (c == '-' || c == '+')
c = scan();
for (; c >= '0' && c <= '9'; c = scan())
val = (val << 3) + (val << 1) + (c & 15);
return neg ? -val : val;
}

}
}

Cleaning Drive solution, Cleaning Drive solution, Cleaning Drive solution, Cleaning Drive solution, Cleaning Drive solution,

Cleaning Drive solution

Also read : Flower Sequence solution codechef 2021 

Leave a Comment