There are N boxes which are 2D in shape. Each box has 2 dimensions, Height denoted by h and Width denoted by w.

A box can fit inside another box if the both the dimensions are strictly smaller. Mathematically, a box i can fit in box j if wi < wj and hi < hj.

A nesting sequence of K length is defined as a sequence of indices p1, p2,….., pk for some integer k ≥ 1 such that pi denotes the element positions from the original array, and the sequence follows the following conditions:

Solution :

Always think this type of problems as 1Dimesional , so if we are given with an array [5,6,5,2,4,1], then if we need to do above like ai < aj , then we simply sort array and find inc subseq , using lowerbound .(LIS standard problem..) ..

But here we are given with 2D , Sort by width ascending, and height descending for same width , if we sort by width asecending , then one problem is not there like , we simply need to find LIS of width , which gives us answer , But what if 2 heights are same , we should not consider them , so we use height by descending such that it never happens. ..

This is same as https://leetcode.com/problems/russian-doll-envelopes/

Fr practice : https://leetcode.com/problems/maximum-length-of-pair-chain/description/

https://leetcode.com/problems/longest-increasing-subsequence/description/