Maximum Length of Pairs in increasing order

Question

Given n pairs of numbers the first number is always smaller than the second number. A pair (c, d) can follow a pair (a, b) if and only if b <= c. Chain of pairs can be formed in this fashion. Find the longest chain which can be formed from a given set of pairs.

e.g. { (1,2), (3,4), (5,7), (9,10), (7,9), (8,9), (0,6) }

So the output should be : {(1,2), (3,4), (5,7), (8,9), (9,10)}

My Algorithm for this is as below:

 1. Sort the list according to the 2nd number of elements
i.e.`{ (1,2), (3,4), (0,6), (5,7), (7,9), (8,9), (9,10)  }`
 2. choose the first element from the list  i.e. `(1,2)`
 3. for each element e in the list left
      4. choose this element e if the first number of the element is greater than the 2nd number of the previous element. i.e. after `(1,2)` choose `(3,4)` because `3 > 2.`

After the above algorithm you will have the output as {(1,2), (3,4), (5,7), (8,9), (9,10)}.

Please let me know about the correctness of the algorithm. Thanks.

EDIT:

A more intuitive proof of correctness:

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.

This is taken from here

Why do you leave the pair (7,9) out? Why does it not come after the pair (5,7)? — arjacsoh, Aug 02 '13 at 14:09
Another valid chain given your example is {(1,2), (3,4), (5,7), (7,9), (9,10)}. Do you desire to find both / all chains, either chain, maximum length chain, or something else? — user1676075, Aug 02 '13 at 14:09
@arjacsoh ya it can come also but either (5,7) or (8,9) can be present at a given point in time. — Trying, Aug 02 '13 at 14:10
@Gamb Are you sure? If that was the case, something like (1, 10000) would still be likely to get into the list — StephenTG, Aug 02 '13 at 14:11
I don't think this will work because it's greedy. There could be a longer chain from excluding one element that is included. I think this needs to be done as a dynamic program. — Boris the Spider, Aug 02 '13 at 14:11
Your algorithm is greedy and won't work for some sets: (1,2) (3,10) (4,5) (6,7) (8,9). Your algorithm will choose (1,2) (3,10). To solve it you must implement dynamic programming algorithm. — gawi, Aug 02 '13 at 14:12
@gawi You're missing the fact that it sorts by second element first — StephenTG, Aug 02 '13 at 14:12
@gawi Agreed. This seems to be a variant on the knapsack problem. — Boris the Spider, Aug 02 '13 at 14:12
@StephenTG Maybe I missed the sorting order - but in general this problem can be solved exactly by DP, not a greedy algorithm — gawi, Aug 02 '13 at 14:14
@gawi first of all it should be sorted on top of the 2nd number of the individual element. — Trying, Aug 02 '13 at 14:15
@gawi With your list, his algorithm should grab (1,2), (4,5), (6,7) (8,9) — StephenTG, Aug 02 '13 at 14:15
This question is asking for a code review not presenting a problem. This question is more suited to CodeReview. — Boris the Spider, Aug 02 '13 at 14:15
@Trying Certainly in that example, as there's no way of fitting (3,10) in anything but a two element chain — StephenTG, Aug 02 '13 at 14:16
For what it's worth, your algorithm is correct. I might post a proof a bit later. — IVlad, Aug 02 '13 at 14:16
OK, Agree, I made a mistake - sorting stuff led me to wrong conclusions - usually you sort to decrease searching space, however in this case you can have to search all pairs anyway, and time complexity in worst case scenario doesn't change — gawi, Aug 02 '13 at 14:23
Why does `(7, 9)` follows `(9,10)` does it violate `b <= c`? — Shivam, Aug 02 '13 at 14:23
@Groo Never said he couldn't. Plus, that's the first step he lists in his algorithm — StephenTG, Aug 02 '13 at 14:24
@Groo - why wouldn't he be? According to his example, the picked pairs do not have to be picked in the relative order that they appear in. — IVlad, Aug 02 '13 at 14:25
@IVlad: right, sorry, I missed that. I thought it was a classic subsequence problem. — vgru, Aug 02 '13 at 14:27
@IVlad: but I still doubt that the optimum solution to this problem always has to start with the element which has the lowest 2nd item? Need to examine it a bit thoroughly, but it just feels strange. — vgru, Aug 02 '13 at 14:29
@Groo Consider a chain `C`, with first element `(c,d)`. Now consider an element (not in the chain) `(a,b)` where `b < d` (thus making it the element with the lowest 2nd item in the new set `{C + (a,b)}`). If `b <= c` then the new element may be added to `C`, making the length longer; if `b > c`, `(c,d)` may be replaced by `(a,b)`, and, because `b b< whatever's next`, the rest of the chain (and thus its length) is unchanged. _One_ of the optimum solutions will start with the element w/ the lowest 2nd item (there may be others, but all the same length). — Reinstate Monica -- notmaynard, Aug 02 '13 at 14:41
@iamnotmaynard: yes, you're right, that makes sense. The fact that it's allowed to pick them in arbitrary order completely screwed my reasoning, but it's actually rather simple. — vgru, Aug 02 '13 at 14:47
@DavidEisenstat and of http://stackoverflow.com/questions/17530303/longest-chain-of-pairs — גלעד ברקן, Aug 02 '13 at 15:44
@DavidEisenstat the link that you have mentioned and this question are not same. Please verify. thanks. — Trying, Aug 02 '13 at 16:21
You're right, it's a duplicate of [this one](http://stackoverflow.com/questions/17530303/longest-chain-of-pairs). — David Eisenstat, Aug 02 '13 at 17:28

score 2 · Accepted Answer · answered Aug 02 '13 at 14:37

It is correct. Here's a proof:

Let s1, s2, ..., sl be the pairs found by your algorithm and i1, i2, ..., ik be an optimal solution.

We have:

l == k => your algorithm is obviously correct, since it's clear that
          it doesn't produce invalid solutions;

l > k => this would contradict our hypothesis that i1, ..., ik is optimal,
         so it makes no sense to bother with this;

l < k => this would mean that your algorithm is wrong. 
         Let's assume this is the case.

Assume i1 != s1. In this case, we can replace i1 with s1 in the optimal solution, since s1 is the pair with the lowest finish time. So s1, i2, ..., ik remains an optimal solution.

Let t <= l be the first index for which st != it. Therefore, s1, s2, ..., s[t-1], it, ... is an optimal solution. We can replace it with st because:

st is not part of the first t-1 elements of the optimal solution;
st is not part of i[t+1], ..., ik. If it were, that would mean that st started after it finished, which would contradict the way the algorithm selects st.

Therefore, continuing in this fashion, our optimal solution is s1, s2, ..., sl, ..., ik. This means that it is possible to add more pairs after sl, but this contradicts the way the algorithm works, so we have l = k, and the algorithm is correct.

Shivam · Answer 2 · 2013-08-02T14:57:04.220

pair (c, d) can follow a pair (a, b) iff b <= c
pair (c, d) has constraint d > c

Therfore we can, say

b <= c

becomes

b < d because d > c

Therefore longest sequence would start with smallest second element. Therefore you sort them according to second element select first element and compare as per your original condition b <= c

Algorithm is correct. As you get the first element (greedy) and then you are keeping the original constraint intact that is b <= c.

Note: You can not use b < d conditions for comparing elements after sorting, because you cannot deduce b <= c (original condition) from b < d but other way around is possible.

i like this proof. more intuitive. +1 – Trying Aug 02 '13 at 16:35 — Trying, Aug 02 '13 at 16:35

Sheel · Answer 3 · 2013-08-02T14:49:45.353

-1

This problem can be solved too many ways Same type of problem is already there check it 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 another pair (a, b) if b < c. Chain of pairs can be formed in this fashion. Find the longest chain which can be formed from a given set of pairs.

You can go here and there are so many useful resource are there

MaximumLengthChainoofPairs

LongestIncreasingSequence

edited Aug 02 '13 at 14:49

answered Aug 02 '13 at 14:19

Sheel

847
2
8
20

1

This is a comment, not an answer. – Joel Aug 02 '13 at 14:21
1

Those are not the same thing because they involve selecting the elements in the order that they appear in. – IVlad Aug 02 '13 at 14:21
@Joel what about(0,6)? – Sheel Aug 02 '13 at 14:50
[@Shivaram Kalra](http://stackoverflow.com/users/858926/shivam-kalra)why not considering(0,6)..this is corner case or longest sequential – Sheel Aug 02 '13 at 14:53
@Envious my algorithm is different from the one that you have posted. I know this can be solved in LIS but this is O(NLogN) algorithm and i feel easier to understand. One more thing i know LIS can be solved in O(NLogN) but thats little bit tricky. Thanks. – Trying Aug 02 '13 at 16:31

Maximum Length of Pairs in increasing order

3 Answers3