Interview Questions/Coding/Archive Envelope Chain

Archive Envelope Chain

Preview mode. Log in to edit, run, submit, and save progress.

Medium

Archive Envelope Chain

An assessment center stores candidate cards inside envelopes. A card can go into an envelope only when both the envelope width and height are strictly larger than the card. Envelopes can then be nested, but every next envelope must again be strictly wider and strictly taller than the previous one. For each batch, report the maximum number of envelopes that can appear in one valid nesting chain around the starting card. Input Format: The first line contains t. Each case starts with n, w, and h: the number of envelopes and the card size. The next n lines contain the width and height of one envelope. Output Format: For each case, print one integer: the maximum valid chain length. Print 0 if no envelope can contain the card.

Examples

Example 1
Input:
2
5 3 3
5 4
6 5
6 7
2 5
7 8
4 4 4
5 5
6 4
4 6
7 7
Output:
3

Explanation: In the first case, three envelopes can be nested after the card. In the second case, the best chain has two envelopes because some envelopes fail one dimension or cannot extend the chain.

Approach hint

Only envelopes strictly larger than the card can start a chain.

Common mistake

Skipping assumptions, edge cases, or trade-offs can make an otherwise good answer feel incomplete.

solution.cpp