Chef Restaurant CodeChef Solution: Chef is a cook and he has recently opened a restaurant.
The restaurant is open during NN time intervals [L1,R1),[L2,R2),…,[LN,RN)[L1,R1),[L2,R2),…,[LN,RN). No two of these intervals overlap — formally, for each valid ii, jj such that i≠ji≠j, either Ri<LjRi<Lj or Rj<LiRj<Li.
MM people (numbered 11 through MM) are planning to eat at the restaurant; let’s denote the time when the ii-th person arrives by PiPi. If the restaurant is open at that time, this person does not have to wait, but if it is closed, this person will wait until it is open. Note that if this person arrives at an exact time when the restaurant is closing, they have to wait for the next opening time.
For each person, calculate how long they have to wait (possibly 00 time), or determine that they will wait forever for the restaurant to open.
Input
- The first line of the input contains a single integer TT denoting the number of test cases. The description of TT test cases follows.
- The first line of the input contains two space-separated integers NN and MM.
- NN lines follow. For each valid ii, the ii-th of these lines contains two space-separated integers LiLi and RiRi.
- MM lines follow. For each valid ii, the ii-th of these lines contains a single integer PiPi.
Output
For each test case, print MM lines. For each valid ii, the ii-th of these lines should contain a single integer — the time person ii has to wait, or −1−1 if person ii has to wait forever.
Constraints
- 1≤T≤1001≤T≤100
- 1≤N,M≤1051≤N,M≤105
- 1≤Li<Ri≤1091≤Li<Ri≤109 for each valid ii
- 1≤Pi≤1091≤Pi≤109 for each valid ii
- the intervals are pairwise disjoint
- the sum of NN for all test cases does not exceed 3⋅1053⋅105
- the sum of MM for all test cases does not exceed 3⋅1053⋅105
Subtasks
Subtask #1 (30 points):
- the sum of NN for all test cases does not exceed 1,0001,000
- the sum of MM for all test cases does not exceed 1,0001,000
Subtask #2 (70 points): original constraints
Sample Input 1
1 4 5 5 7 9 10 2 3 20 30 5 6 7 35 1
Sample Output 1
0 2 -1 1
Chef Restaurant CodeChef Solution in JAVA
import java.util.*;
import java.lang.*;
import java.io.*;
/* Name of the class has to be "Main" only if the class is public. */
class Codechef
{
static class FastScanner {
BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st=new StringTokenizer("");
String next() {
while (!st.hasMoreTokens())
try {
st=new StringTokenizer(br.readLine());
} catch (IOException e) {
e.printStackTrace();
}
return st.nextToken();
}
int nextInt() {
return Integer.parseInt(next());
}
int[] readArray(int n) {
int[] a=new int[n];
for (int i=0; i<n; i++) a[i]=nextInt();
return a;
}
long nextLong() {
return Long.parseLong(next());
}
}
public static long solve (long[] arr, long t) {
int start = 0;
int end = (arr.length / 2) - 1;
while (start <= end) {
int mid = start + (end - start) / 2;
if (arr[(start * 2) + 1] > t) {
if (arr[start * 2] - t <= 0)
return 0;
else
return arr[start * 2] - t;
}
else if (arr[(mid * 2) + 1] > t) {
end = mid;
start = start + 1;
}
else
start = mid + 1;
}
return -1;
}
public static void main (String[] args) throws java.lang.Exception
{
// your code goes here
FastScanner sc = new FastScanner();
int tc = Integer.parseInt(sc.next());
while (tc-- != 0) {
int n = Integer.parseInt(sc.next());
int m= Integer.parseInt(sc.next());
long[] arr1 = new long[2 * n];
long[] arr2 = new long[m];
for (int j = 0; j < 2 * n; j++) {
arr1[j] = sc.nextLong();
}
Arrays.sort(arr1);
for (int j = 0; j < m; j++) {
arr2[j] = sc.nextLong();
}
for (int j = 0; j < m; j++) {
if (arr2[j] > arr1[arr1.length - 1]) {
System.out.println("-1");
}
else
System.out.println(solve(arr1, arr2[j]));
}
}
}
}
Chef Restaurant CodeChef Solution in CPP
#include <bits/stdc++.h>
using namespace std;
int main() {
int t;
cin>>t;
while(t--)
{
int n,m;
cin>>n>>m;
vector<pair<int,int>> v(n);
for(int i=0;i<n;i++)
{
int s,e;
cin>>s>>e;
v[i]=make_pair(s,e);
}
sort(v.begin(),v.end());
while(m--)
{
int curr_time;
cin>>curr_time;
long long position=lower_bound(v.begin(),v.end(),make_pair(curr_time,0))-v.begin();
if(position==0)
{
int ans=v[position].first-curr_time;
cout<<ans<<endl;
}
else
{
if(v[position-1].second>curr_time)
cout<<"0\n";
else if(position<v.size())
cout<<v[position].first-curr_time<<endl;
else
cout<<"-1\n";
}
}
}
return 0;
}
Chef Restaurant CodeChef Solution in Python
# cook your dish here
t=int(input())
for _ in range(t):
n,m=map(int,input().split())
lst=[]
for __ in range(n):
a,b=map(int,input().split())
lst.append([a,b])
lst.sort(key=lambda x:x[0])
#print(lst)
for __ in range(m):
curr=int(input())
si=0
ei=n-1
ans=-1
while si<=ei:
mid=(si+ei)//2
if lst[mid][0]<curr:
si=mid+1
elif lst[mid][0]>curr:
ei=mid-1
ans=mid
else:
ans=mid
break
#print(ans,end=" ")
if ans==-1:
if lst[n-1][0]<=curr and lst[n-1][1]>curr:
print(0)
else:
print(-1)
else:
if ans==0:
print(lst[ans][0]-curr)
else:
if lst[ans-1][0]<=curr and lst[ans-1][1]>curr:
print(0)
else:
print(lst[ans][0]-curr)
Disclaimer: The above Problem (Chef Restaurant) is generated by CodeChef but the solution is provided by Chase2learn.This tutorial is only for Educational and Learning purpose.