I dont understand at timestamp 2:50

#1

how to check that no of workers can complete work in 70 minutes or not ? can u explain with example ?

#2

Hey Premang, to check whether k painters can finish job in t time can be done greedily such that no painter paints boards whose sum is greater than t, whenever sum exceeds given t value,we assign current board to new painter (if new painter exists or k>0), else we say it is impossible to do job in t time.
example: we have 4 boards : 20 30 10 40, k=2
lets check for t=40
1 painter - 20 (cant do next board as sum exceeds 40!)
2 painter - 30 10 (cant do next board as sum exceeds 40)
now as 1 more board is left,we say job cannot be completed in t=40
similarly for t=50
1 painter = 20,30
2 painter = 10,40
hence it is possible to do it in t=50

#3

my approach, can u tell me whats the problem with this ?

#include
#include
using namespace std;
int main() {
int k;
cin >> k;

int n;
cin >> n;

int arr[n],maxx=INT_MIN;
for(int i=0;i<n;i++) {
    cin >> arr[i];
    maxx=max(maxx,arr[i]);
}

cout << maxx << endl;

return 0;

}

i can pass half of the test cases , then why we need binary search ?

#4

it is not necessary that maximum arr[i] is answer. This is a monotonic problem which means that if some x satisfy the constraints, then x+1,x+2,… will also satisfy the constraints, in such type of problems we use binary search as it gives complexity of logN order.

#5

I hope I’ve cleared your doubt. I ask you to please rate your experience here
Your feedback is very important. It helps us improve our platform and hence provide you
the learning experience you deserve.

On the off chance, you still have some questions or not find the answers satisfactory, you may reopen
the doubt.