Job Sequencing Problem | Greedy Algorithms
HTML-код
- Опубликовано: 17 янв 2021
- Check our Website:
In case you are thinking to buy courses, please check below:
Link to get 20% additional Discount at Coding Ninjas: bit.ly/3wE5aHx
Code "takeuforward" for 15% off at GFG: practice.geeksforgeeks.org/co...
Code "takeuforward" for 20% off on sys-design: get.interviewready.io?_aff=takeuforward
Crypto, I use the Wazirx app: wazirx.com/invite/xexnpc4u
Take 750 rs free Amazon Stock from me: indmoney.onelink.me/RmHC/idje...
Earn 100 rs by making a Grow Account for investing: app.groww.in/v3cO/8hu879t0
Linkedin/Instagram/Telegram: linktr.ee/takeUforward
---------------------------------------------------------------------------------------------------------------------------------------------------- I have decided to make a free placement series comprising of video lectures(C++ and Java) on the entire SDE sheet.. ✅(bit.ly/takeUforward_SDE)
✅Entire Series: bit.ly/placementSeries
✅Problem link: practice.geeksforgeeks.org/pr...
C++/Java Code: takeuforward.org/data-structu...
✅Unacademy has launched a subscription that will help you learn and interact with your favorite teacher and will also help you clear your doubts! Check it out here: unacademy.com/goal/competitiv... (use coupon code TAKEUFORWARD to get 10% off)
Join Unacademy's Pinnacle 2021; A Comprehensive and Concise Track to Become an Expert: unacademy.com/batch/pinnacle-...
Check out Unacademy’s Free Classes and tests here (For Desktops):
www.codechef.com/cptutorials?...
unacademy.com/test-series/pro...
unacademy.com/a/tech-placemen...
✅This is where I teach: ----- Use coupon-code "TAKEUFORWARD" for getting 10% on my course at GFG: bit.ly/striver_cpCourse
✅Use coupon-code "TAKEUFORWARD" for getting 10% for all GFG courses: bit.ly/tuf_gfgCourse
If you appreciate the channel's work, you can join the family: bit.ly/joinFamily
Thumbnail Creator: / rikonakhuli
✅ Striver's Linkedin Profile: / rajarvp
✅ Instagram: / striver_79
Connect with us: t.me/Competitive_Programming_tuf (Use Link in Mobile only, if not works search "takeUforward" in telegram)..
#dsa #leetcode #placements
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. 🙌
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. :)
Yes🙃
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
UNDERSTOOD... !!!
Thanks striver for the video... :)
Please continue the playlist..
Which approach does interviewer asks
The one that you taught or the disjoint set approach
@TakeUForward As per the explanation, the result array should contain (result[j] = arr[i].id) in line 71 of java code
Can we solve it using knapsack method if we sort by deadline in ascending order?
Understood.........Thank You So Much for this wonderful video.......🙏🏻🙏🏻🙏🏻🙏🏻🙏🏻🙏🏻🙏🏻🙏🏻
instead of disjoint set u can use normal set too to it in nlogn
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?
A Big Big THANKS for your contribution♥
Thanks bro for the nice and clear explanation.
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
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
can anyone tell what is the base of log when we are discussing time complexity?
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 understood the solution and intuition!
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.
The way of solving question 💯
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
for correct job sequence put slot[j]=arr[i].id; on line 47 c++ code
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.
thank you so much very good understanding
Understood. Thank you!
Thank you so much!!!!!!!!!!!!
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 ??
Striver, you are the saviour!!!!
Thank you, striver!
@take U forward can you please explain nlogn solution for this problem
easy and concise explanation
best video ,related to greedy on the internet.
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???
Striver, you are awesome. Thanks a ton.
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
Thank you bhaiya!!❤️✨
where can I get the code?
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
Brilliant wat an explanation
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.
it took me 2 days to get a grasp on problem statement l
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.
how to perform this sort?
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.
Understood!
Understood
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
Variables are "guys" 😄jokes apart, Thanks a lot for the content and really appreciate the hardwork 😇
Where is brute force i.e. DP approach!???
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
Hey brother
All the best for the surgery.
What surgery?
Understood sir
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?
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.
understood
Thanks sir
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;
}
Understood 💯💯💯
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?
understood bhaiya
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
Understood 😇
line 36 i will start from 1
🔥🔥
thanks strivers
got it
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?
Yeah bro +1
Like mind! Looking for the same.
Can I??
c++ 15:10
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.
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
cool 🆒 🔥🔥🔥🔥
💘
🙌🙌🔥🔥
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};
}
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 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
Bhaiya voice phat rhi hai apki
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
😍😍😍
😁
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
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.
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
😍