Maximum chain length of pairs || Dynamic programming

[@rakshith3547]

Best part about your videos are the clarity of taught with which you are explaining. I can clearly convert to code at one go without any issues.

[@techdose4u]

Nice :)

[@sahoosiddharth]

Hey, you know what, your videos are really good. But I am sad to see such low views on your videos, But don't worry Keep uploading and helping students like me. The day will come you will be recognised by many of us. Kepp hurtling. BTW I am an aspiring SDE, currently in 4th year with no placement offer in hand. Totally fucked up and trying to figure out my way to Big product based company but sadly I am a very average student with high aspiration and trying hard to learn DS and algo and doing coding. I hope your videos will help me catch my dream.

[@techdose4u]

I don't really worry about figures for now. I just want to help others figure a way out of their difficult times. Thanks for your motivation BTW. One thing which I can tell you is that the people working for big MNCs are average themselves. Those who are extraordinary find their own career and setup their own business or company. So don't worry about being average because most of the world population is average themselves. It's just the will power and devotion towards your passion which will lead to your success. It depends on how badly you want something and work for it. Keep working, there is always time to achieve success :)

[@sahoosiddharth]

@@techdose4u Thank you for showing your kind gesture to reply on my comment. Just Keep motivating me with your amazing videos. And kindly cover all the problem from easy to adv level which is highly asked in coding interviews. Thank you once again.

[@techdose4u]

On my way of doing it :)

[@sitapriyanka5452]

TECH As. m

[@techdose4u]

Need any help?

[@HarishAmarnath]

Guys we can do this in O(n) time...by greedy method. Pls refer activity selection problem in geeks for geeks.

[@impatientgaming9868]

Good one

[@raysdev]

The longest chain length of 3 is correct but the actual pairs output of [15, 28] -> [39, 60] -> [50,90] is incorrect as [39, 60] overlaps w/ [50, 90]. The correct pairs that do not overlap at all since the ending time of previous pair has to be strictly less than the starting time of the next pair would be [5, 24] -> [27,40] -> [50,90] You would need to adjust the algo for reverse engineering the actual pairs that are valid non-overlapping intervals by taking the latter & not first when traversing backwards.

[@rakshith3547]

while calculating time complexity are we not considering Arrays.sort() which we do in order to sort the input?

[@techdose4u]

Sorting will take NlogN. The optimal approach which I talked about at the end is using Sorting + 1 traversal. The method I showed was using LIS Dynamic programming. Even if you consider sorting, time will still be the same.

[@ritikakosigi9176]

thank you so much

[@aishwantghimire7607]

Why are we sorting here but not in LIS problem?

[@techdose4u]

LIS involves ordering should be maintained. Sorting will make it unordered.

[@ArunGangula93]

how does [{50, 90}, {39, 60}, {15, 28}] pass the condition {a, b} {c, d} where c > b

[@randomclicks6466]

Yes it will not work he didn't notice

[@kingaakashgoswami7735]

#include using namespace std; int main() { vectorchain = {{50, 90}, {39, 60}, {15, 2}}; int n = chain.size(); sort(chain.begin(),chain.end()); vectordp(n,1); for(int i=1;i

[@mohitbhargava7839]

{15,28},{39,60}

[@nervynithya2406]

yes, only the last 2 in 2's and last 1 in 1's while traversing from right works.

[@nervynithya2406]

@@kingaakashgoswami7735 But sorting algorithm itself takes O(N log N) time complexity here

[@ashishmh]

Still couldn't get why we need the LIS condition. If you can share the intuition behind the second condition, that would make things clearer.

[@surendharv795]

Refer to LIS video in his channel and you will get the clarity.

[@sumitjindal1115]

Nice explanation sir....please make videos on backtracking and greedy.

[@manthankhorwal1477]

Why sorting with first value or the second value givess the same answer?

[@aditikajale8514]

yes same ans

[@harshitsharma1880]

//O(N*logN) The structure to use is as follows struct val{ int first; int second; };*/ bool comp(val v1,val v2) { return v1.second

[@sumedhkane1365]

Intuition bta de bhai

[@shamshuddinshaik2218]

Bro plz make next video on combination of array elements with r elements {1,2,3} and r= 2 then output: 1 2 1 3 2 3

[@techdose4u]

Okay sure..... :)

[@shamshuddinshaik2218]

@@techdose4u tnq bro..

[@techdose4u]

Can you please mention the entire question..... Because only a slight change in question can make the entire code different...... Also you need to print all possible combinations of a given array of numbers I guess where order doesn't matter. Example, 3,1 and 1,3 are same right? Please mention the entire problem clearly then I will make it :)

[@shamshuddinshaik2218]

@@techdose4u www.google.com/amp/s/www.geeksforgeeks.org/print-all-possible-combinations-of-r-elements-in-a-given-array-of-size-n/amp/

[@techdose4u]

I will make it soon.

[@eshanchourasia287]

Why are we sorting?

[@chodingninjas7415]

More videos please

[@techdose4u]

Stay tuned :)

[@utubecom9185]

Solution wih nlogn Or give some hint???

[@aneeshkulkarni1739]

Similar to patience sort technique.

[@arnavkarforma3015]

leetcode.com/problems/maximum-length-of-pair-chain/solution/

[@arnavkarforma3015]

public int findLongestChain(int[][] pairs) { Arrays.sort(pairs, (a, b) -> a[1] - b[1]); int cur = Integer.MIN_VALUE, ans = 0; for (int[] pair: pairs) if (cur < pair[0]) { cur = pair[1]; ans++; } return ans; }

[@vanshmoza2212]

Sort the input based on the ending time, then iterate over the array check the condition if the element at index has start greater than the previous, if yes then just increment the counter and return the counter at last. (Greedy approach- category activity selection problem)

[@niteshagarwal4934]

It is not working fo rthis case {(6, 8),(3,4)} oputput is coming 1 which should be 2

[@manojpandey7517]

Did you sort the array?

[@abhaytiwari6411]

please solve this question with python practicaly

[@techdose4u]

Code with python will be the same as in cpp. You just sort the array and make a list (filled with 1 initially). Then follow LIS code. It will be done. Try harder. You can solve it. If you still face problem then let me know.

[@sitapriyanka5452]

TECHNICALLY I don’t DOSE v

[@techdose4u]

?? Do you want to ask something ?

[@harshraj57]

Starting value se sort karne par ans galt aa raha kyu?

[@ahmadzeed591]

I put dislike because you didn't explain what questions need good ,i don't understand how the output

[@techdose4u]

This problem is similar to minimum platforms problem. Please see that and if you don't understand then read the pinned comment in that problem (given by Wang). That will clear your doubt for sure. If you still face problem then let me know. I will help you.

[@alokkumarsingh282]

Will this logic work for the input {5, 10} {11, 7} {6, 8} {9, 10} ? The best answer here is 4. But i think your algorithm will find it as 3

[@HarishAmarnath]

Your input is wrong..start value MUST be smaller than end value

[@awesome_latest_virals6098]

please introduce yourself in a separate video

[@techdose4u]

Okay sure

[@nikhilprasad644]

bhai logic toh de kyu aisa karr rahhe hai, algo gfg se dekh k batana hai toh video kyu banna raha hai, sabb logic dekhne aate hai . try to give logic in ur videos. video me mehnat karr yaar, why waste time of students