leetcode [1377] T 秒后青蛙的位置

---

Contact me:

Blog -> https://cugtyt.github.io/blog/index
Email -> cugtyt@qq.com
GitHub -> Cugtyt@GitHub

---

给出一个无重叠的 ，按照区间起始端点排序的区间列表。

在列表中插入一个新的区间，你需要确保列表中的区间仍然有序且不重叠（如果有必要的话，可以合并区间）。

示例 1:

输入: intervals = [[1,3],[6,9]], newInterval = [2,5]
输出: [[1,5],[6,9]]

示例 2:

输入: intervals = [[1,2],[3,5],[6,7],[8,10],[12,16]], newInterval = [4,8]
输出: [[1,2],[3,10],[12,16]]
解释: 这是因为新的区间 [4,8] 与 [3,5],[6,7],[8,10] 重叠。

class Solution:
    def frogPosition(self, n: int, edges: List[List[int]], t: int, target: int) -> float:
        edges = [sorted(edge) for edge in edges]
        edges.sort()
        index = -1
        edges.insert(0, [0, 1])
        for i in range(len(edges)):
            if edges[i][1] == target:
                index = i
                break
        if index == -1:
            return 0
        
        parent = edges[index][0]
        index_, parent_ = index, parent
        prob = 1
        while parent != 0:
            t -= 1
            left, right = index, index
            while left >= 0 and edges[left][0] == parent:
                left -= 1
            while right < len(edges) and edges[right][0] == parent:
                right += 1
            left = left + 1
            prob *= 1 / (right - left)
            for i in range(left - 1, -1, -1):
                if edges[i][1] == parent:
                    index = i
                    parent = edges[i][0]
                    break

        if t < 0: return 0
        if t == 0: return prob
        if t > 0:
            for i in range(index_, len(edges)):
                if edges[i][0] == target:
                    return 0
            return prob