<p>You are given an array of <code>n</code> pairs <code>pairs</code> where <code>pairs[i] = [left<sub>i</sub>, right<sub>i</sub>]</code> and <code>left<sub>i</sub> &lt; right<sub>i</sub></code>.</p>

<p>A pair <code>p2 = [c, d]</code> <strong>follows</strong> a pair <code>p1 = [a, b]</code> if <code>b &lt; c</code>. A <strong>chain</strong> of pairs can be formed in this fashion.</p>

<p>Return <em>the length longest chain which can be formed</em>.</p>

<p>You do not need to use up all the given intervals. You can select pairs in any order.</p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>

<pre>
<strong>Input:</strong> pairs = [[1,2],[2,3],[3,4]]
<strong>Output:</strong> 2
<strong>Explanation:</strong> The longest chain is [1,2] -&gt; [3,4].
</pre>

<p><strong class="example">Example 2:</strong></p>

<pre>
<strong>Input:</strong> pairs = [[1,2],[7,8],[4,5]]
<strong>Output:</strong> 3
<strong>Explanation:</strong> The longest chain is [1,2] -&gt; [4,5] -&gt; [7,8].
</pre>

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>n == pairs.length</code></li>
	<li><code>1 &lt;= n &lt;= 1000</code></li>
	<li><code>-1000 &lt;= left<sub>i</sub> &lt; right<sub>i</sub> &lt;= 1000</code></li>
</ul>

void print_arr(const vector<int>& arr){
    cout << "[ ";
    for(int elm:arr){ cout << elm << " "; }
    cout << "]";
}
void print_adj_lists(const vector<vector<int>>& adj_list){
    for(const vector<int>& arr:adj_list){ print_arr(arr);cout << endl; }
}
class Graph{
public:
    int num_vert;
    vector<vector<int>> adj_lists;
    vector<int> max_path_len;
    Graph(int num_vert):num_vert(num_vert),adj_lists(num_vert),max_path_len(num_vert,-1){}
    void add_edge(int from,int to){ adj_lists[from].push_back(to); }
    int max_path_len_help(int cur_vert){
        int max_child_len = 1;
        for(int nghbr:adj_lists[cur_vert]){
            if(max_path_len[nghbr] == -1){ max_path_len_help(nghbr); }
            max_child_len = max(max_child_len,1+max_path_len[nghbr]);
        } 
        max_path_len[cur_vert] = max_child_len;
        return max_child_len;
    }
    int max_path(){
        int max_path = 1;
        for(int i=0;i<num_vert;i++){
            if(max_path_len[i] == -1){ max_path_len_help(i); }    
            max_path = max(max_path,max_path_len[i]);
        }
        return max_path;
    }
};
bool pair_compare(const vector<int>& a,const vector<int>& b){
    if(a[1] < b[0]){ return true; }
    return false;
}
class Solution {
public:
    int findLongestChain(vector<vector<int>>& pairs) {
        int size = pairs.size();
        Graph g(size);
        for(int i=0;i<size;i++){
            for(int j=0;j<size;j++){
                if(pair_compare(pairs[i],pairs[j])){
                    g.add_edge(i,j);
                }
            }
        }
        //print_adj_lists(g.adj_lists);
        return g.max_path();
    }
};
83510