Maximum Length of Pair Chain - Leetcode 646 - Python

Solving Maximum length of pair chain, today's daily leetcode problem. It's similar to the Longest Increasing Subsequence problem, but can be solved more easily with a clever approach.

0:00 - Read the problem
3:08 - DP Explanation
5:39 - Greedy Explanation
11:30 - Coding Greedy solution

leetcode 646

#neetcode #leetcode #python

[akshaykhatri]

The DP solution could also be O(nlogn) if we sort the intervals first.
Sort by start times then scan through the intervals from end to start and find the first interval on right side that has start time greater than end of current interval (using binary search). Also, the dp array would store the max length of all the subarrays on right so far, not just the length of current chain

[ankurgoswami]

it's just a variation of Longest Increasing Subsequence (LIS)

[КонстантинОсипов-иб]

It is a brilliant solution! I understood it after I tried to do it myself

[kareni]

Thanks for the interval solution. It's probably similar to non - overlapping intervals maybe?

[swanv]

I always find it difficult to justify whether a greedy approach is correct or not

[bird_in_hat]

Thanks! But explanation on 9:00 is too intense, bro.

[yang]

Holy shit this is meeting rooms all over again

[aazzrwadrf]

Didn't find channel this until recently. I missed a lot of vids..

[reggiehurley]

why is the solution so f-ing easy but impossible to figure out???