<reponame>chrisxue815/leetcode_python
import unittest
from typing import List

import utils


# O(nlog(n)) time. O(1) space. Interval, sorting by end, greedy.
class Solution:
    def findLongestChain(self, pairs: List[List[int]]) -> int:
        if not pairs:
            return 0

        pairs.sort()
        num_non_overlaps = 0
        prev_end = pairs[0][0] - 1

        for start, end in pairs:
            if prev_end < start:
                num_non_overlaps += 1
                prev_end = end
            else:
                prev_end = min(prev_end, end)

        return num_non_overlaps


class Test(unittest.TestCase):
    def test(self):
        cases = utils.load_test_json(__file__).test_cases

        for case in cases:
            args = str(case.args)
            actual = Solution().findLongestChain(**case.args.__dict__)
            self.assertEqual(case.expected, actual, msg=args)


if __name__ == '__main__':
    unittest.main()
