{"id":"58f6ed29-fe99-43e3-9f2c-6f3ceb7ca337","name":"Russian Doll Envelopes","description":"1. You are given a number n, representing the number of envelopes.\r\n2. You are given n pair of numbers, representing the width and height of each envelope.\r\n3. You are required to print the count of maximum number of envelopes that can be nested inside each other.\r\nNote -> Rotation is not allowed.","inputFormat":"A number n\r\n.. n pair of number each on a separate line (and pair separated by space)","outputFormat":"A number representing the count of maximum number of envelopes that can be nested inside each other.","constraints":"0 <= n <= 20\r\n0 <= n1w, n1h, n2w, n2h, .. <= 100","sampleCode":{"cpp":{"code":""},"java":{"code":"import java.io.*;\r\nimport java.util.*;\r\n\r\npublic class Main {\r\n\r\n public static void main(String[] args) throws Exception {\r\n // write your code here\r\n }\r\n\r\n}"},"node":{"code":""},"ruby":{"code":""},"python":{"code":""}},"points":10,"difficulty":"hard","sampleInput":"11\r\n17 5\r\n26 18\r\n25 34\r\n48 84\r\n63 72\r\n42 86\r\n9 55\r\n4 70\r\n21 45\r\n68 76\r\n58 51","sampleOutput":"5","questionVideo":"https://www.youtube.com/embed/Mud_QjUwbw8?end=187","hints":[],"associated":[],"solutionSeen":false,"tags":[],"meta":{"path":[{"id":0,"name":"home"},{"id":"0c54b191-7b99-4f2c-acb3-e7f2ec748b2a","name":"Data Structures and Algorithms","slug":"data-structures-and-algorithms","type":0},{"id":"5539a6e8-c8bf-4f04-805c-e43e9d20e72a","name":"Dynamic Programming For Intermediate","slug":"dynamic-programming-for-intermediate-408","type":0},{"id":"7c0491c0-468f-4a92-b0f8-e9ccc66d7579","name":"Russian Doll Envelopes","slug":"russian-doll-envelopes","type":1}],"next":{"id":"0fb02aff-fb20-4773-85a8-02e2388a1414","name":"Catalan Number","type":1,"slug":"catalan-number"},"prev":{"id":"8eccc981-b420-4757-8668-f75aba7d2b3f","name":"Longest Palindromic Substring","type":1,"slug":"longest-palindromic-substring"}}}

Russian Doll Envelopes

1. You are given a number n, representing the number of envelopes. 2. You are given n pair of numbers, representing the width and height of each envelope. 3. You are required to print the count of maximum number of envelopes that can be nested inside each other. Note -> Rotation is not allowed.

{"id":"58f6ed29-fe99-43e3-9f2c-6f3ceb7ca337","name":"Russian Doll Envelopes","description":"1. You are given a number n, representing the number of envelopes.\r\n2. You are given n pair of numbers, representing the width and height of each envelope.\r\n3. You are required to print the count of maximum number of envelopes that can be nested inside each other.\r\nNote -> Rotation is not allowed.","inputFormat":"A number n\r\n.. n pair of number each on a separate line (and pair separated by space)","outputFormat":"A number representing the count of maximum number of envelopes that can be nested inside each other.","constraints":"0 <= n <= 20\r\n0 <= n1w, n1h, n2w, n2h, .. <= 100","sampleCode":{"cpp":{"code":""},"java":{"code":"import java.io.*;\r\nimport java.util.*;\r\n\r\npublic class Main {\r\n\r\n public static void main(String[] args) throws Exception {\r\n // write your code here\r\n }\r\n\r\n}"},"node":{"code":""},"ruby":{"code":""},"python":{"code":""}},"points":10,"difficulty":"hard","sampleInput":"11\r\n17 5\r\n26 18\r\n25 34\r\n48 84\r\n63 72\r\n42 86\r\n9 55\r\n4 70\r\n21 45\r\n68 76\r\n58 51","sampleOutput":"5","questionVideo":"https://www.youtube.com/embed/Mud_QjUwbw8?end=187","hints":[],"associated":[],"solutionSeen":false,"tags":[],"meta":{"path":[{"id":0,"name":"home"},{"id":"0c54b191-7b99-4f2c-acb3-e7f2ec748b2a","name":"Data Structures and Algorithms","slug":"data-structures-and-algorithms","type":0},{"id":"5539a6e8-c8bf-4f04-805c-e43e9d20e72a","name":"Dynamic Programming For Intermediate","slug":"dynamic-programming-for-intermediate-408","type":0},{"id":"7c0491c0-468f-4a92-b0f8-e9ccc66d7579","name":"Russian Doll Envelopes","slug":"russian-doll-envelopes","type":1}],"next":{"id":"0fb02aff-fb20-4773-85a8-02e2388a1414","name":"Catalan Number","type":1,"slug":"catalan-number"},"prev":{"id":"8eccc981-b420-4757-8668-f75aba7d2b3f","name":"Longest Palindromic Substring","type":1,"slug":"longest-palindromic-substring"}}}
plane

Editor

Loading...

Russian Doll Envelopes

hard

1. You are given a number n, representing the number of envelopes. 2. You are given n pair of numbers, representing the width and height of each envelope. 3. You are required to print the count of maximum number of envelopes that can be nested inside each other. Note -> Rotation is not allowed.

Constraints

0 <= n <= 20 0 <= n1w, n1h, n2w, n2h, .. <= 100

Format

Input

A number n .. n pair of number each on a separate line (and pair separated by space)

Output

A number representing the count of maximum number of envelopes that can be nested inside each other.

Example

Sample Input

11 17 5 26 18 25 34 48 84 63 72 42 86 9 55 4 70 21 45 68 76 58 51

Sample Output

5

Question Video

Discussions

Show Discussion

Related Resources

related resources

Turning Off Zen Mode