A Classical Problem?

Revision en1, by JianfengZhu, 2023-05-19 11:51:17

You are given a permutation of $$$n$$$. Build an undirected graph of $$$n$$$ nodes. There is an edge $$$(i,j)$$$ if and only if $$$i<j$$$ and $$$p_i < p_j$$$. Please find the maximum matching of the graph.

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en2 English JianfengZhu 2023-05-19 11:51:55 47 Tiny change: 'the graph.' -> 'the graph.\n\nI don't know how to do it in $O(n \log n)$.'
en1 English JianfengZhu 2023-05-19 11:51:17 205 Initial revision (published)