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.
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
@@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
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.
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 ?
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.
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. 😢
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
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
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.
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 ??
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; }
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; } };
@@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.
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 < arr.length; 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
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
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
@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.
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.
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
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
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
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
You make difficult concepts look easy.... Crystal clear explanation as always ❤
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!
I felt so difficult to do this problem, but the way you have explained made it simple to think. 🙌
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.
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
Sort the array and apply 2 pointer technique to find the pairs.
It is similar to two sum problem
Instead of sorting method use a frequency array which will make the solution O(n) instead of nlogn with n space complexity
@@rishabmudliar558 the array elements can be negative so,so we cannot take frequency array
@@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
Your explanation skills are insane!! Thanks a ton. :)
Yes🙃
Please continue the playlist..
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.
Understood.........Thank You So Much for this wonderful video.......🙏🏻🙏🏻🙏🏻🙏🏻🙏🏻🙏🏻🙏🏻🙏🏻
@TakeUForward As per the explanation, the result array should contain (result[j] = arr[i].id) in line 71 of java code
for correct job sequence put slot[j]=arr[i].id; on line 47 c++ code
best video ,related to greedy on the internet.
instead of disjoint set u can use normal set too to it in nlogn
UNDERSTOOD... !!!
Thanks striver for the video... :)
I was expecting priority queue solution from you for O(NlogN) time complexity
usko samjh hi nahi aya hoga .lol
@@neerajchoudhary3709 you probably don't know who he's
@@devrajgoswami4357 He's what he is! Striver_79
did u get the solution in this time complexity
@@simitoor1 I think MinHeap would do that
In c++ code shouldn't we store arr[i].index in slot[j] according to solution explained earlier?
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.
Yes. That would be better if they ask u to print the job sequence.
A Big Big THANKS for your contribution♥
Striver, you are the saviour!!!!
GOD LEVEL EXPLANATION!!!!
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 ?
yeah
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.
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. 😢
This is a hard level question not easy
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
The way of solving question 💯
I understood the solution and intuition!
easy and concise explanation
Can we solve it using knapsack method if we sort by deadline in ascending order?
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?
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
Hey brother
All the best for the surgery.
What surgery?
Thank you bhaiya!!❤️✨
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
yes, you are right !! i was thinking the same
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
For the sort_arr function, return "a.profit > b.profit" instead of "a.profit >= b.profit"
@@divyasreedev6460 It worked..thanks a lot :)
@@ankitgarg3247 You're welcome
@@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?
it took me 2 days to get a grasp on problem statement l
Understood. Thank you!
Thanks bro for the nice and clear explanation.
Which approach does interviewer asks
The one that you taught or the disjoint set approach
Thank you, striver!
Striver, you are awesome. Thanks a ton.
thank you so much very good understanding
Brilliant wat an explanation
Variables are "guys" 😄jokes apart, Thanks a lot for the content and really appreciate the hardwork 😇
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.
Then write in your local code editor na bhai
Hey Striver, Can you upload a video on Roti-Prata Spoj problem please? Thanks in advance !!
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
c++ 15:10
if profits aare same, we should not sort deadline by ascending order?
Deadline wont matter since both of them will be having same profit and anyone after that will hace lesser profit.
Understood 💯💯💯
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
Thank you so much!!!!!!!!!!!!
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};
}
Understood sir
Time complexity is O(N^2) or O(N*logN) + O(N*M) ?
Yeah i also thing, because there is one more loop inside to find the proper index
N logN is for sorting
N*M is identifying the slot
Why N^2 term??
@@karthikpaladugula5424 if M=N-1(Worst Case) then complexity for identifying the slot will become N*(N-1) ~N^2
max value of deadline (m) is 100, hence it will not be O(n*m)
@@omkar.gaikwad how?
@take U forward can you please explain nlogn solution for this problem
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 ??
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;
}
can anyone tell what is the base of log when we are discussing time complexity?
Understood 😇
Understood!
where can I get the code?
Understood
line 36 i will start from 1
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;
}
};
thanks strivers
how to perform this sort?
Thanks sir
Where is brute force i.e. DP approach!???
understood bhaiya
What if each job takes more than 1 unit of time?
Then from the back allocate that much time, simple!
"Each job takes 1 unit of time to complete" 0:25
@@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.
@@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
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.
understood
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 < arr.length; 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};
}
got it
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
code kudse kar bhai . aur kon video dekhega iska tension mat le
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
Telegram pe text kr do, ek hi text krna mentioning unban on telegram
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
S.erase takes o(n),
Refer www.cplusplus.com/reference/set/set/erase/
@@takeUforward ohhh I didn't know... Thank you for correcting me 🙏
@@nisarggogate8952I think TUF is not correct. s.erase of a range is only O(n), else it is O(logn). Check the link.
@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.
@@takeUforward I think erasing in set using an iterator take O(1) time so it has O(nlogn) time complexity.
On submitting this solution on gfg it's showing Runtime error for C++.
They have changed the problem..
bhai ab try kar, ab submit ho jaayega
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.
🔥🔥
cool 🆒 🔥🔥🔥🔥
Needed a competitive coding partner with whom I can start my competitive coding journey .Anyone interested please reply?
Yeah bro +1
Like mind! Looking for the same.
Can I??
🙌🙌🔥🔥
💘
😍
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
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
Your comparator function is wrong.
how can you return j1.deadline
Why fear when Java is here use lamda function
Bhaiya voice phat rhi hai apki
😍😍😍
😁
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