You make difficult concepts look easy.... Crystal clear explanation as always ❤

I felt so difficult to do this problem, but the way you have explained made it simple to think. 🙌

C++ Code Link: github.com/striver79/SDESheet/blob/main/jobSequencingCpp Java Code Link: github.com/striver79/SDESheet/blob/main/jobSequencingJava Live sessions on Insta: striver_79

It's weird, I was able to get the logic once you visualized everything, I should focus on visualizing my thought process much more or elaborately I guess, thanks a lot!

Nailed it striver. Thank you for the awesome explanation. The clever part is doing the job (which can be done till very late) on the last deadline unit (if the last deadline unit for the job is not occupied or just as before the last deadline unit which is not occupied) so that in the meantime you can complete the other jobs and maintaining this using a visited array.

Your explanation skills are insane!! Thanks a ton. :)

@yutaitadori7318

3 жыл бұрын

Yes🙃

UNDERSTOOD... !!! Thanks striver for the video... :)

since we know that values will be integers can we use a stable non comparison based sorting algorithm and bring sorting complexity down to linear

Please continue the playlist..

Can we solve it using knapsack method if we sort by deadline in ascending order?

A Big Big THANKS for your contribution♥

@TakeUForward As per the explanation, the result array should contain (result[j] = arr[i].id) in line 71 of java code

Great work dada!! I found a question recently asked in amazon.. Given an integer array arr of size N and an integer S. Return the list of all pairs of elements such that for each sum of elements of each pair equals to S. Note: Each pair should be sorted i.e the first value should be less than or equals to the second value. Return the list of pairs sorted in non-decreasing order of their first value. In case if two pairs have the same first value, the pair with a smaller second value should come first. Input Format: The first line of input contains two space-separated integers N and S, denoting the size of the input array and the value of S. The second and last line of input contains N space-separated integers, denoting the elements of the input array: arr[i] where 0

@manideepaktelaprolu3073

3 жыл бұрын

Sort the array and apply 2 pointer technique to find the pairs.

@yatinarora1252

3 жыл бұрын

It is similar to two sum problem

@rishabmudliar558

2 жыл бұрын

Instead of sorting method use a frequency array which will make the solution O(n) instead of nlogn with n space complexity

@pawankumarnandagiri8202

2 жыл бұрын

@@rishabmudliar558 the array elements can be negative so,so we cannot take frequency array

@VinayKumar-ze2ww

Жыл бұрын

@@pawankumarnandagiri8202 unordered map is useful then Interviewer can ask for returning indices rather than values, and if we sort array, we won't find the answer

Which approach does interviewer asks The one that you taught or the disjoint set approach

Thanks bro for the nice and clear explanation.

instead of disjoint set u can use normal set too to it in nlogn

The way of solving question 💯

Understood.........Thank You So Much for this wonderful video.......🙏🏻🙏🏻🙏🏻🙏🏻🙏🏻🙏🏻🙏🏻🙏🏻

I understood the solution and intuition!

for correct job sequence put slot[j]=arr[i].id; on line 47 c++ code

Understood. Thank you!

Striver, you are the saviour!!!!

I can't even solve this easy question on my own. I have to watch the video for almost every single problem on SDE sheet 😔 I want to be SDE in a big tech company but now losing hope. 😢

@shadaabiqbal4875

6 ай бұрын

This is a hard level question not easy

In c++ code shouldn't we store arr[i].index in slot[j] according to solution explained earlier?

@shubhamsood1406

3 жыл бұрын

We can do that also, we only have to change the array value from -1 to any other number, both ways of changing the array value is correct.

@manavshah7450

3 жыл бұрын

Yes. That would be better if they ask u to print the job sequence.

can anyone tell what is the base of log when we are discussing time complexity?

After solving this question, I came here to look for the best solution and guess what it is what exactly I did, thank you so much for your videos that I am getting better everyday.

can we just sort it based on deadline (primary) and then sort it based on profit(secondary) That will just require linear time after sorting

Thank you, striver!

easy and concise explanation

Thank you so much!!!!!!!!!!!!

best video ,related to greedy on the internet.

Thank you bhaiya!!❤️✨

Bhaiya, I was trying to solve it using DSU but I am not getting a correct answer. Can you please make a video on it if possible?

Striver, you are awesome. Thanks a ton.

Hey Striver, Can you upload a video on Roti-Prata Spoj problem please? Thanks in advance !!

Brilliant wat an explanation

Sir, how are you editing GFG default code? For me, the main function is already there and I just have to write the function only, but I want to write the code from scratch.

@ScienceSeekho

Жыл бұрын

Then write in your local code editor na bhai

GOD LEVEL EXPLANATION!!!!

I was expecting priority queue solution from you for O(NlogN) time complexity

@neerajchoudhary3709

2 жыл бұрын

usko samjh hi nahi aya hoga .lol

@devrajgoswami4357

Жыл бұрын

@@neerajchoudhary3709 you probably don't know who he's

@supriyamanna715

Жыл бұрын

@@devrajgoswami4357 He's what he is! Striver_79

@simitoor1

Жыл бұрын

did u get the solution in this time complexity

@supriyamanna715

Жыл бұрын

@@simitoor1 I think MinHeap would do that

I have done like this in C language - #include #include #include typedef enum{true,false}bool; typedef struct{ char id; int deed; int profit; }job; int deed(const void *p1 , const void *p2){ const job *pa=p1; const job *pb=p2; return pb->deed - pa->deed; } int compare(const void *p1 , const void *p2){ const job *pa=p1; const job *pb=p2; return pb->profit - pa->profit; } int funC(int max,bool a[]){ int i=0; if(max>1){ for(i=max-1;i>=0;i--){ if(a[i]==false){ return i+1; } } } return 0; } int main() { job arr[]={{'a',2,40},{'b',2,30},{'c',4,20},{'d',1,70}}; int size=sizeof(arr)/sizeof(arr[0]); qsort(arr,size,sizeof(arr[0]),deed); int max=arr[0].deed; qsort(arr,size,sizeof(arr[0]),compare); for(int i=0;i

in the question's example, we are not performing the job on the deadline which is not given, and in the video answers to deadline 3 are not given but we are performing the job on day 3 ...this is something that question changes???

suppose if there are 5 jobs and all have deadline 5, and 5 is the maximum deadline among all, then for each and every deadline we've to check like this - 1+2+3+4+......(n-1) = O(n^2), isn't it

Bhai agar profits same ho toh phir id choose karneka kya? Just like we did in N meetings question or deadline like jiski deadline pehle voh pehle aise kuch ??

let's consider the case after sorting job id deadline profit 2 3 a[j=3] 500 4 3 a[j=2] 400 2 3 a[j=1] 300 1 3 j=3 to1 200 from here you starting the j =3 loop till 1 but in array 3,2,1 index already filled 2 5 -> 100 This is the max deadline case so in next i th iteration you filled this in array 2 1 50 but in this case profit, 200 skips and 100 is considered instead of 200 this is fine ?

@alokdwivedi2

Жыл бұрын

yeah

@venkateshvenky2880

Жыл бұрын

100 is having enough time to solve later , so is included.

Is it wrong if we sort on the basis of deadline but for equal deadlines we sort on the basis of profit. That way we'll be able to finish the jobs that are expiring first but also accepting the jobs that have more profit first.

it took me 2 days to get a grasp on problem statement l

Understood!

where can I get the code?

@take U forward can you please explain nlogn solution for this problem

if profits aare same, we should not sort deadline by ascending order?

@takeUforward

3 жыл бұрын

Deadline wont matter since both of them will be having same profit and anyone after that will hace lesser profit.

Understood

how to perform this sort?

Understood sir

Thanks sir

Variables are "guys" 😄jokes apart, Thanks a lot for the content and really appreciate the hardwork 😇

Hey brother All the best for the surgery.

@Saikumar-kb4lf

3 жыл бұрын

What surgery?

understood

Understood 💯💯💯

Understood 😇

understood bhaiya

if(result[j]==-1){ result[j]=arr[i].id; (replacing from result[j]=i; bcz in intuition part you said to store job id) count++; jobprofit+=arr[i].profit; break; }

🔥🔥

thanks strivers

got it

I wrote the same code.. but it is giving runtime error on GFG. Can anybody point out the mistake? class Solution { public: static bool sort_arr(Job a, Job b) { return a.profit >= b.profit; } //Function to find the maximum profit and the number of jobs done. vector JobScheduling(Job arr[], int n) { sort(arr, arr+n, sort_arr); int size = arr[0].dead; for(int i=1; i

@divyasreedev6460

2 жыл бұрын

For the sort_arr function, return "a.profit > b.profit" instead of "a.profit >= b.profit"

@ankitgarg3247

2 жыл бұрын

@@divyasreedev6460 It worked..thanks a lot :)

@divyasreedev6460

2 жыл бұрын

@@ankitgarg3247 You're welcome

@btRohit-st9jp

Жыл бұрын

@@divyasreedev6460 hey can you help me i am not getting the reason why ">=" not work if we have same profit which one come before don't matter na?

Time complexity is O(N^2) or O(N*logN) + O(N*M) ?

@shashikantkumar5095

3 жыл бұрын

Yeah i also thing, because there is one more loop inside to find the proper index

@karthikpaladugula5424

3 жыл бұрын

N logN is for sorting N*M is identifying the slot Why N^2 term??

@akshitarora3524

3 жыл бұрын

@@karthikpaladugula5424 if M=N-1(Worst Case) then complexity for identifying the slot will become N*(N-1) ~N^2

@omkar.gaikwad

Жыл бұрын

max value of deadline (m) is 100, hence it will not be O(n*m)

@MayankLC93

Жыл бұрын

@@omkar.gaikwad how?

Where is brute force i.e. DP approach!???

way of explanation is good but code is complicate. shradha khapra code is more crisp and short .and more easy to understand but dp series is amazing

line 36 i will start from 1

🙌🙌🔥🔥

💘

Striver the comparison function need to be declared as static then it is running why so? please reply. i am also an condition if (jobCount == maxi) break; so that if jobcount is equal to maxi then no free slot is remaining so stop.

c++ 15:10

What if each job takes more than 1 unit of time?

@takeUforward

3 жыл бұрын

Then from the back allocate that much time, simple!

@thelimit9719

3 жыл бұрын

"Each job takes 1 unit of time to complete" 0:25

@devangrajarora7002

3 жыл бұрын

​@@takeUforward I don't think that would work in the case where unit of time taken unit. For example, Job 1: Profit: 50, deadline: 5, time: 5 Job 2: Profit: 30, deadline: 5, time: 3 Job 3: Profit: 20, deadline: 5, time: 2 Now here we should perform Job 2 and Job 3 instead of just Job 1.

@yatinarora1252

3 жыл бұрын

@@devangrajarora7002 I think job 1 should be done as it is having maximum profit.Simply just we will be doing job1 for continous 5 days

@manavshah7450

3 жыл бұрын

Just fill that many slots which is equal to the job time. It will work. And about your example question. Job 1 will be selected and that is correct.

cool 🆒 🔥🔥🔥🔥

Can someone please tell me what is wrong in this code...Only 12 cases are passed class Solution { public: static bool comparator(Job a,Job b) { return (a.profit>b.profit); } //Function to find the maximum profit and the number of jobs done. vector JobScheduling(Job arr[], int n) { int maxDeadline=arr[0].dead; sort(arr,arr+n,comparator); for(int i=1;imaxDeadline) { maxDeadline=arr[i].dead; } } vectorv(maxDeadline+1,-1);int profit=0; int c=0; for(int i=0;i0;j--) { if(v[j]==-1) { profit+=arr[i].profit; v[j]=arr[i].id; c++; break; } } } vectorans; ans.push_back(c); ans.push_back(profit); return ans; } };

Needed a competitive coding partner with whom I can start my competitive coding journey .Anyone interested please reply?

@_var.onwheels

3 жыл бұрын

Yeah bro +1

@ghoshdipan

3 жыл бұрын

Like mind! Looking for the same.

@koushikbiswas8289

2 жыл бұрын

Can I??

Bhaiya please consider me back to the telegram channel , I also tried to contact to u through instagram , please bhaiya consider my request and I haven't spoke anything bad and abusive and negative through out the duration for which , I was a member of that telegram channel

@takeUforward

3 жыл бұрын

Telegram pe text kr do, ek hi text krna mentioning unban on telegram

C++ #include using namespace std; vector jobScheduling(vector &jobs){ sort(jobs.begin(), jobs.end(), [](vector& a, const vector& b) { return a[2] > b[2]; }); int cnt = 0, profit = 0, n = jobs.size(); vector take(n+1, false); for(auto &job : jobs){ for(int i=job[1] - 1; i>=0; i--){ if(!take[i]){ take[i] = true; cnt++; profit += job[2]; break; } } } return {cnt, profit}; }

On submitting this solution on gfg it's showing Runtime error for C++.

@takeUforward

2 жыл бұрын

They have changed the problem..

@411_danishranjan9

2 жыл бұрын

bhai ab try kar, ab submit ho jaayega

😍😍😍

public static int[] JobScheduling(Job arr[], int n) { int ans = 0; int count = 0; int doIt[] = new int[101]; Arrays.sort(arr, (a, b) -> Integer.compare(b.profit, a.profit)); for (int i = 0; i int j = arr[i].deadline; while (j > 0 && doIt[j] != 0) j--; if (j > 0) { count++; ans += arr[i].profit; doIt[j] = arr[i].deadline; } } return new int[]{count, ans}; }

😁

bhaiya foreign me koi nhi dekhta hoga apki video😭😭😭plz plz hindi me samjhya kijiye. and plz code in java as well in some of your video you use only cpp and you are famous for writing code in both languages. and truly logic samajh aaya ,, lekin code nhi

@Ak-um1yg

Жыл бұрын

code kudse kar bhai . aur kon video dekhega iska tension mat le

Here is a soln with sets. Making time complexity O(NlogN). The soon by TUF was of O(N^2) vector JobScheduling(Job arr[], int n) { sort(arr,arr+n,compare); set s; int ans = 0,i; for(i=1;i

@takeUforward

3 жыл бұрын

S.erase takes o(n), Refer www.cplusplus.com/reference/set/set/erase/

@nisarggogate8952

3 жыл бұрын

@@takeUforward ohhh I didn't know... Thank you for correcting me 🙏

@arshad1679

2 жыл бұрын

@@nisarggogate8952I think TUF is not correct. s.erase of a range is only O(n), else it is O(logn). Check the link.

@MrShaundan

2 жыл бұрын

@take U forward For the first version (erase(position)), amortized constant. For the second version (erase(val)), logarithmic in container size. For the last version (erase(first,last)), linear in the distance between first and last.

@RaviSingh-qd5pz

2 жыл бұрын

@@takeUforward I think erasing in set using an iterator take O(1) time so it has O(nlogn) time complexity.

Bhaiya voice phat rhi hai apki

hello sir can we sort the array with increasing order of deadline and if deadline is same then sort it according to max profit something like this. struct Job { int Deadline; int id; int profit; } static bool comp(Job j1,Job j2) { if(j1.deadline!=j2.deadline) return j1.profit>j2.profit; else return j1.deadline

@kartikeyaagrawal5917

3 жыл бұрын

it would have been right if the question said that the person doing the job cannot complete before the deadline .here in the question it is up to the person how he shedules his work. Say in ur case task 1(deadline 1day) has some profit "a" and task 2 (deadline 2) with profit "b" & task 3 with(deadline = 2) and profit c .Say here c>b>a in such a case ur program will choose task 3 and task 1 profit as a+c; but suppose he completes task 2 on day one and task 3 on day 2 he will ear b+c which is >a+c

@manavshah7450

3 жыл бұрын

Your comparator function is wrong. how can you return j1.deadline

@aj9706

2 жыл бұрын

Why fear when Java is here use lamda function

bkl ka code python mein nhi chlta

what is problem with my code can someone explain vector JobScheduling(Job arr[], int n) { if(n==0) { return {0,0}; } else if(n==1) { return {1,arr[0].profit}; } int maxi=1; priority_queuepq; for(int i=0;i=1) { if(res[k]==-1||res[k]=1) { res[j-1]=res[j]; j--; } res[k]=profit; res[0]=-1; break; } k--; } } int count=0; int maxprofit=0; for(int i=1;i

shoudn't it be slot[j] = arr[i].id;

slot[j]=arr[i].id

Thank you bhaiya!!❤️✨

Understood!

Understood

understood

😍