Loading problem...
You are given a collection of n intervals, where each interval is represented as a pair [start, end] with the constraint that start < end.
An interval q = [c, d] can be linked after another interval p = [a, b] if and only if b < c. In other words, the second interval must begin strictly after the first interval ends. A sequence of intervals is formed by linking intervals one after another following this rule.
Your task is to determine the maximum length of such a sequence that can be formed using the given intervals.
Key Observations:
pairs = [[1,2],[2,3],[3,4]]2We cannot link [1,2] → [2,3] because 2 is not strictly less than 2 (the end of [1,2] equals the start of [2,3]). However, we can form the sequence [1,2] → [3,4] which has length 2. This is the maximum achievable length.
pairs = [[1,2],[7,8],[4,5]]3All three intervals can be linked: [1,2] → [4,5] → [7,8]. The end of [1,2] is 2, which is less than 4 (start of [4,5]). The end of [4,5] is 5, which is less than 7 (start of [7,8]). Thus, the maximum sequence length is 3.
pairs = [[1,5],[2,4],[6,10],[8,12]]2The intervals [1,5] and [2,4] overlap in their ranges, so we can only choose one of them. Similarly, [6,10] and [8,12] overlap. The best sequence is either [1,5] → [6,10] or [2,4] → [6,10] or [2,4] → [8,12], each with length 2.
Constraints