# You are given a series of video clips from a sporting event that lasted T seconds.  These video clips can be
# overlapping with each other and have varied lengths.
#
# Each video clip clips[i] is an interval: it starts at time clips[i][0] and ends at time clips[i][1].  We can cut
# these clips into segments freely: for example, a clip [0, 7] can be cut into segments [0, 1] + [1, 3] + [3, 7].
#
# Return the minimum number of clips needed so that we can cut the clips into segments that cover the entire sporting
# event ([0, T]).  If the task is impossible, return -1.
#
#
#
# Example 1:
#
# Input: clips = [[0,2],[4,6],[8,10],[1,9],[1,5],[5,9]], T = 10
# Output: 3
# Explanation:
# We take the clips [0,2], [8,10], [1,9]; a total of 3 clips.
# Then, we can reconstruct the sporting event as follows:
# We cut [1,9] into segments [1,2] + [2,8] + [8,9].
# Now we have segments [0,2] + [2,8] + [8,10] which cover the sporting event [0, 10].
# Example 2:
#
# Input: clips = [[0,1],[1,2]], T = 5
# Output: -1
# Explanation:
# We can't cover [0,5] with only [0,1] and [0,2].
# Example 3:
#
# Input: clips = [[0,1],[6,8],[0,2],[5,6],[0,4],[0,3],[6,7],[1,3],[4,7],[1,4],[2,5],[2,6],[3,4],[4,5],[5,7],[6,9]],
# T = 9
# Output: 3
# Explanation:
# We can take clips [0,4], [4,7], and [6,9].
# Example 4:
#
# Input: clips = [[0,4],[2,8]], T = 5
# Output: 2
# Explanation:
# Notice you can have extra video after the event ends.
#
#
# Note:
#
# 1 <= clips.length <= 100
# 0 <= clips[i][0], clips[i][1] <= 100
# 0 <= T <= 100
import collections


class Solution(object):
    def videoStitching(self, clips, T):
        """
        :type clips: List[List[int]]
        :type T: int
        :rtype: int
        """

        # first sort by starting pos, then sort end pos reversely
        # for ex, [0,4], [4,6],[4,7],[4,8],[2,3],[3,5], after sort
        # it is [0,4], [2,3],[3,5],[4,8],[4,7],[4,6]
        # why I sort like this way? because if we have [4,8], then we can quickly eliminate [4,7] and [4,6]
        def comparator(i1, i2):
            if i1[0] == i2[0]:
                return i2[1] - i1[1]
            return i1[0] - i2[0]

        clips.sort(comparator)
        # print clips

        st = []

        for t in clips:
            # using stack, assume we have [4,8] in st, then [4,7] and [4,6] won't be there
            # so [0,4], [2,3],[3,5],[4,8],[4,7],[4,6] would become [0,4], [2,3],[3,5],[4,8]
            if st and t[1] > st[-1][1] or not st:
                st.append(t)
        # print st

        res, mapping, prev, cur = 0, {}, 0, 0

        for s in st:
            mapping[s[0]] = s[1]

        i = 0
        for i in xrange(0, T + 1):
            if i > cur:
                return -1
            if i > prev:
                prev, res = cur, res + 1
            if i in mapping:
                cur = max(cur, mapping[i])

        return res if i >= T else -1

    # this algo is the same as jump game II, greedy
    def videoStitching_wihoutsort(self, clips, T):
        """
        :type clips: List[List[int]]
        :type T: int
        :rtype: int
        """
        mDict = collections.defaultdict(int)

        for c in clips:
            mDict[c[0]] = max(mDict[c[0]], c[1])

        i, res, prev, cur = 0, 0, 0, 0
        for i in xrange(0, T + 1):
            if i > cur:
                return -1
            if i > prev:
                prev, res = cur, res + 1
            if i in mDict:
                cur = max(cur, mDict[i])

        return res



if __name__ == '__main__':
    print Solution().videoStitching([[8, 10], [17, 39], [18, 19], [8, 16], [13, 35], [33, 39], [11, 19], [18, 35]], 20)
    print Solution().videoStitching_wihoutsort(
        [[8, 10], [17, 39], [18, 19], [8, 16], [13, 35], [33, 39], [11, 19], [18, 35]], 20)
    print Solution().videoStitching([[5, 7], [1, 8], [0, 0], [2, 3], [4, 5], [0, 6], [5, 10], [7, 10]], 5)
    print Solution().videoStitching_wihoutsort([[5, 7], [1, 8], [0, 0], [2, 3], [4, 5], [0, 6], [5, 10], [7, 10]], 5)
    print Solution().videoStitching([[0, 4], [2, 8]], 5)
    print Solution().videoStitching_wihoutsort([[0, 4], [2, 8]], 5)
    print Solution().videoStitching(
        [[0, 5], [1, 6], [2, 7], [3, 8], [4, 9], [5, 10], [6, 11], [7, 12], [8, 13], [9, 14], [10, 15], [11, 16],
         [12, 17], [13, 18], [14, 19], [15, 20], [16, 21], [17, 22], [18, 23], [19, 24], [20, 25], [21, 26], [22, 27],
         [23, 28], [24, 29], [25, 30], [26, 31], [27, 32], [28, 33], [29, 34], [30, 35], [31, 36], [32, 37], [33, 38],
         [34, 39], [35, 40], [36, 41], [37, 42], [38, 43], [39, 44], [40, 45], [41, 46], [42, 47], [43, 48], [44, 49],
         [45, 50], [46, 51], [47, 52], [48, 53], [49, 54]], 50)
    print Solution().videoStitching_wihoutsort(
        [[0, 5], [1, 6], [2, 7], [3, 8], [4, 9], [5, 10], [6, 11], [7, 12], [8, 13], [9, 14], [10, 15], [11, 16],
         [12, 17], [13, 18], [14, 19], [15, 20], [16, 21], [17, 22], [18, 23], [19, 24], [20, 25], [21, 26], [22, 27],
         [23, 28], [24, 29], [25, 30], [26, 31], [27, 32], [28, 33], [29, 34], [30, 35], [31, 36], [32, 37], [33, 38],
         [34, 39], [35, 40], [36, 41], [37, 42], [38, 43], [39, 44], [40, 45], [41, 46], [42, 47], [43, 48], [44, 49],
         [45, 50], [46, 51], [47, 52], [48, 53], [49, 54]], 50)
    print Solution().videoStitching([[0, 1], [1, 2]], 5)
    print Solution().videoStitching_wihoutsort([[0, 1], [1, 2]], 5)
    print Solution().videoStitching(
        [[17, 18], [25, 26], [16, 21], [3, 3], [19, 23], [1, 5], [0, 2], [9, 20], [5, 17], [8, 10]], 15)
    print Solution().videoStitching_wihoutsort(
        [[17, 18], [25, 26], [16, 21], [3, 3], [19, 23], [1, 5], [0, 2], [9, 20], [5, 17], [8, 10]], 15)
    print Solution().videoStitching(
        [[8, 12], [14, 20], [18, 19], [2, 8], [17, 19], [7, 17], [6, 19], [8, 12], [10, 17]], 10)
    print Solution().videoStitching_wihoutsort(
        [[8, 12], [14, 20], [18, 19], [2, 8], [17, 19], [7, 17], [6, 19], [8, 12], [10, 17]], 10)
    print Solution().videoStitching([[3, 12], [7, 14], [9, 14], [12, 15], [0, 9], [4, 14], [2, 7], [1, 11]], 10)
    print Solution().videoStitching_wihoutsort([[3, 12], [7, 14], [9, 14], [12, 15], [0, 9], [4, 14], [2, 7], [1, 11]],
                                               10)
    print Solution().videoStitching([[5, 7], [1, 8], [0, 0], [2, 3], [4, 5], [0, 6], [5, 10], [7, 10]], 5)
    print Solution().videoStitching_wihoutsort([[5, 7], [1, 8], [0, 0], [2, 3], [4, 5], [0, 6], [5, 10], [7, 10]], 5)
    print Solution().videoStitching(
        [[0, 1], [6, 8], [0, 2], [5, 6], [0, 4], [0, 3], [6, 7], [1, 3], [4, 7], [1, 4], [2, 5], [2, 6], [3, 4], [4, 5],
         [5, 7], [6, 9]], 9)
    print Solution().videoStitching_wihoutsort(
        [[0, 1], [6, 8], [0, 2], [5, 6], [0, 4], [0, 3], [6, 7], [1, 3], [4, 7], [1, 4], [2, 5], [2, 6], [3, 4], [4, 5],
         [5, 7], [6, 9]], 9)
    print Solution().videoStitching([[0, 2], [4, 6], [8, 10], [1, 9], [1, 5], [5, 9]], 10)
    print Solution().videoStitching_wihoutsort([[0, 2], [4, 6], [8, 10], [1, 9], [1, 5], [5, 9]], 10)
    print Solution().videoStitching([[0, 1], [1, 2]], 5)
    print Solution().videoStitching_wihoutsort([[0, 1], [1, 2]], 5)
