<commit_before>import unittest
import utils


# O(nlog(n)) time. O(n) space. Sort, greedy.
class Solution:
    def findLongestChain(self, pairs):
        """
        :type pairs: List[List[int]]
        :rtype: int
        """
        if not pairs:
            return 0

        pairs.sort(key=lambda x: x[1])
        result = 1
        prev = pairs[0][1]

        for i in range(1, len(pairs)):
            if prev < pairs[i][0]:
                prev = pairs[i][1]
                result += 1

        return result


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()
<commit_msg>646. Maximum Length of Pair Chain<commit_after>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(key=lambda pair: pair[1])
        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

        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()

{'fraction_non_alphanumeric': 0.11061946902654868, 'fraction_numerical': 0.011061946902654867, 'mean_word_length': 2.071307300509338, 'pattern_counts': {'":': 0, '<': 5, '<?xml version=': 0, '>': 4, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'dir': 'git-commits-cleaned', 'id': '2985573', 'n_tokens_mistral': 580, 'n_tokens_neox': 552, 'n_words': 144}