Longest chain of pairs

Question

You are given n pairs of numbers. In every pair, the first number is always smaller than the second number. A pair (c,d) can follow (a,b) if and only if b is less than c. Chains of pairs can be formed in this manner. Find the longest chain of pairs formed.

I got this question in an interview with Amazon but couldn't figure out the answer, just that it is related to the LIS problem.

Answer 1

Because the two values of each (X,Y) pair must be in order (X < Y), and the Y value of one pair must be less than the X value of the next pair, you are essentially building one continuous chain of values along one dimension. You just need to sort by the Y values.

Given this sample data:

(15,40) (5,8) (1,10) (6,8) (9,20) (2,4) (36,37) (34,35) (9,14) (30,31)

Sort by Y to get:

(2,4) (6,8) (5,8) (1,10) (9,14) (9,20) (30,31) (34,35) (36,37) (15,40)

Then loop through, adding a pair to the chain if its X is greater than the last Y in the chain, and ignoring it otherwise.

Notice that in this example, (6,8) happened to be sorted before (5,8). It doesn't matter which pair is chosen for the chain when their Y values are equal, as long as the X value satisfies the condition of being greater than the previous Y.

Here's a diagram showing the sorted pairs as bars above a number line. Starting at the first pair, (2,4), each one that is added to the chain at the bottom is colored yellow. Visually, the gray ones are skipped because there's a yellow one "in the way" of it being dropped into the chain (overlapping values).

Proof: The only way to include more pairs in the chain is to replace a pair with one with a smaller Y value, to allow for the next pair to have a smaller X value, potentially fitting another pair where it couldn't fit before. If you replace a pair with one with the same Y value, you gain nothing. If the replacement has a larger Y value, all you've done is potentially block some pairs that would've fit before.

Because the pairs have been sorted by Y values, you will never find a replacement with a smaller Y. Looking "forward" in the sorted pairs, they will all have the same or greater Y value. Looking "backward", any that were eliminated from the chain initially were because the X value wasn't high enough, which will still be the case.

Answer 2

First, this problem can be viewed as plotting points on a two dimensional grid where x co-ordinate of each point is less than y co-ordinate of that point. Now you're asked to find the longest chain such that every i+1 th point is both above and to the right of the ith point (and the y co-ordinate of the ith point is less than x co-ordinate of i+1th point).

now let's sort the points first based on their x co-ordinate. Then we start visiting the sorted points from lowest x co-ordinate, if there's a tie for x co-ordinate then we'll visit points with higher y co-ordinate first. now for an example if we're working on the ith point, we know that all points already visited have lower or similar x co-ordinate of the ith one. So the longest chain end at point i will be the longest chain that we've already got with y co-ordinate<=x co-ordinate of the current point.

We can do it efficiently with an efficient data structure like segment tree or Binary indexed tree.

Runtime of this solution is : O(NlgN) where N is the number of points (pairs in the given problem).

Answer 3

A basic way to solving this problem would be to create a tree, where each node is a pair, and construct directed edges from one node to another when it is legal (ie, "A pair (c,d) can follow (a,b) if and only if b is less than c"). You can do a modified breadth first traversal from each node that keeps track of the length of the longest path from that node, and when you are finished with that can just look over all the nodes to find the longest path.