ARTS #49

Algorithm

本周选择的算法题是：Video Stitching

规则如下：

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

Solution

Runtime：28 ms，快过 91.26%。

Memory：13.9 MB，低于 50%。

class Solution:
    def videoStitching(self, clips: List[List[int]], T: int) -> int:
        if T == 0: return 0
        clips.sort(key=lambda x: (x[0], x[1]))
        if clips[0][0] != 0: return -1
        ans = [clips[0]]

        for i in range(1, len(clips)):
            clip = clips[i]
            if ans[-1][1] >= T: break
            if ans[-1][0] == clip[0] and ans[-1][1] < clip[1]:
                ans[-1] = clip
            else:     
                if len(ans) > 1 and ans[-2][1] >= clip[0] and clip[1] >= ans[-1][1]:
                    ans.pop()
                if clip[1] > ans[-1][1]:
                    if clip[0] <= ans[-1][1]:
                        ans.append(clip)
                    else:
                        return -1
        return len(ans) if ans[-1][1] >= T else -1

附上一个非常 elegant 的实现：

class Solution:
    def videoStitching(self, clips: List[List[int]], T: int) -> int:
        end1, end2, ans = -1, 0, 0
        for clip in sorted(clips):
            if end2 >= T or clip[0] > end2: break
            if end1 < clip[0] <= end2:
                ans, end1 = ans + 1, end2
            end2 = max(end2, clip[1])

        return ans if end2 >= T else -1

不记录完整的解，只记录最后两个 clip 的 [1]。

Review

What Is Redux: A Designer’s Guide

这篇文章重点介绍了：

什么是状态
- State is data that change from time to time
什么是状态管理 / 为什么需要状态管理
为什么了解它对设计师有帮助
- Optimistic UI / 积极的用户界面
Redux 可以在编程世界里广泛应用

全篇没有代码，没有编程经验的人看完也可以理解什么是 Redux，以及它能做什么。对它的目标用户（设计师）友好，稍显不足的是在 Why 上不够深入。

Tip

通过符号或者内存地址查询 image 信息：

image lookup -v -n databaseWithPath:
image lookup -v --address 0x100123aa3

检查 macho 中是否包含 debug 信息：

objdump -h xxx | grep debug_info

通过 Python 脚本获取 Compile Unit 信息：

LLVM - Troubleshooting

LLVM - Symbolication

二进制化后的源码调试方案总结整理：

zsource - 在美团内部使用了半年以上后方案被公开了出来，工具链的一部分，高度集成、无侵入性、易落地
lldb - lldb 入坑指北（2）- 15行代码搞定二进制与源码映射，原理和 zsource 差不多，对下载到本地的源码位置没有要求，不过有些前置工作需要人工来做，无侵入性、易落地
sourcePod - iOS组件化过程中的源码查看，相比前两种实现方式需要在运行时介入，该方法将源码下载时机提前到了 Pod 集成时，可以在调试期间查看源码

Algorithm

Solution

Review

Tip

Share