DDSA Solutions

646. Maximum Length of Pair Chain

MediumView on LeetCode
ArrayDynamic ProgrammingSorting
Time: O(n log n)
Space: O(1)

Problem Overview

Greedy: sort by end value.

Intuition

Greedy: sort by end value. Greedily select the chain pair whose end is smallest (classic interval scheduling).

Algorithm

  1. 1Sort pairs by their end (second) value.
  2. 2curr = pairs[0], count = 1.
  3. 3For each subsequent pair p: if p.start > curr.end, take it: count++, curr=p.

Common Pitfalls

  • •Sort by end value, not start value. Strictly greater (not >=) to extend the chain.
646.cs
C#
// Approach: Greedy — sort pairs by their end value; always pick the next
// pair whose start exceeds the last selected pair’s end.
// Time: O(n log n) Space: O(1)

public class Solution
{
    public int FindLongestChain(int[][] pairs)
    {
        int n = pairs.Length;
        Array.Sort(pairs, (a, b) => a[1] - b[1]);

        // for(int i = 0; i < n; i++)
        // {
        //     Console.WriteLine("Pair " + i + " : " + pairs[i][0] + " " + pairs[i][1]);
        // }

        int maxi = 1;
        int[] last = pairs[0];
        for (int i = 1; i < n; i++)
        {
            if (pairs[i][0] > last[1])
            {
                last = pairs[i];
                maxi++;
            }
        }

        return maxi;
    }
}
Was this solution helpful?

Related Problems