leetcode/leetcode/lc0646_maximum-length-of-pair-chain.py at master · catinthecode/leetcode · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
"""
646. Maximum Length of Pair Chain
Medium

1453

89

Add to List

Share
You are given an array of n pairs pairs where pairs[i] = [lefti, righti] and lefti < righti.

A pair p2 = [c, d] follows a pair p1 = [a, b] if b < c. A chain of pairs can be formed in this fashion.

Return the length longest chain which can be formed.

You do not need to use up all the given intervals. You can select pairs in any order.


Example 1:

Input: pairs = [[1,2],[2,3],[3,4]]
Output: 2
Explanation: The longest chain is [1,2] -> [3,4].
Example 2:

Input: pairs = [[1,2],[7,8],[4,5]]
Output: 3
Explanation: The longest chain is [1,2] -> [4,5] -> [7,8].


Constraints:

n == pairs.length
1 <= n <= 1000
-1000 <= lefti < righti < 1000

"""
import math
from typing import List

"""
Greedy

sort by end time, try to use next pair that will end first

mistakes:
1. start time curp should be -math.inf, not 0, since we have negative numbers
"""


class Solution:
    def findLongestChain(self, pairs: List[List[int]]) -> int:
        pairs = sorted(pairs, key=lambda x: x[1])

        ans = 0
        curp = -math.inf
        for p0, p1 in pairs:
            # print('curp=%s p0=%s p1=%s' % (curp, p0, p1))
            if p0 > curp:
                ans += 1
                curp = p1
                # print('ans=%s using (%s, %s)' % (ans, p0, p1))

        return ans


def main():
    sol = Solution()
    assert sol.findLongestChain(pairs = [[1,2],[2,3],[3,4]]) == 2, 'fails'

    assert sol.findLongestChain(pairs = [[1,2],[7,8],[4,5]]) == 3, 'fails'


if __name__ == '__main__':
   main()