1、区间合并问题（排序+遍历，100%）

手机在同一时间运行多款App。假设当后台没有App在运行时，手机进入休眠；否则手机处于运行状态。
第i个App的开始运行时间starti，运行结束时间endi，组成第i个App的运行区间intervals[i] = [starti, endi]。
数组intervals表示今天米小兔的mix fold 2的各个App的运行区间的集合，求今天米小兔的手机运行了多长时间

输入：
1 3
2 6
8 10
15 18
输出：
10

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        List<long[]> list = new ArrayList<>();
        while (scanner.hasNextLine()) {
            String s = scanner.nextLine();
            if ("".equals(s)) {
                break;
            }
            String[] time = s.trim().split("\\s+");
            long[] t = new long[]{Long.parseLong(time[0]), Long.parseLong(time[1])};
            list.add(t);
        }
        // 排序
        list.sort((a, b) -> {
            if (a[0] == b[0]) {
                return (int) (a[1] - b[1]);
            }
            return (int) (a[0] - b[0]);
        });
        long ans = 0;
        long lastEnd = 0;
        for (long[] t : list) {
            if (t[0] >= lastEnd) {
                ans += t[1] - t[0];
            } else if (t[1] > lastEnd) {
                ans += t[1] - lastEnd;
            }
            lastEnd = Math.max(t[1],lastEnd);
        }
        System.out.println(ans);
    }
}

2、动态规划（100%）

老师发给米小兔一串排列好的卡片，
每个卡片上都有一个英文字母，组成的字符串为s。
老师要求，米小兔可以通过增加卡片、抽出卡片、替换卡片的方式（26个英文字母均可替换），
将卡片排列成目标字符串t。你能算一算，米小兔最少需要操作几次吗？

输入：
"horse"
"ros"
输出：
3

总感觉做过类似的题，但当时想不起来了，就硬写，写得有点丑。有些情况应该可以合并。

public class Main2 {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        String s = scanner.nextLine();
        String t = scanner.nextLine();
        int n = s.length();
        int m = t.length();
        // dp[i][j]：s的前i个字符变为t的前j个字符的最小操作次数
        int[][] dp = new int[n + 1][m + 1];
        for (int i = 0; i <= n; i++) {
            dp[i][0] = i;
        }
        for (int j = 0; j <= m; j++) {
            dp[0][j] = j;
        }
        for (int i = 1; i <= n; i++) {
            char ch1 = s.charAt(i-1);
            for (int j = 1; j <= m; j++) {
                char ch2 = t.charAt(j-1);
                if (i == j) {
                    if (ch1 == ch2) {
                        dp[i][j] = dp[i - 1][j - 1];
                    } else {
                        // 替换
                        dp[i][j] = dp[i - 1][j - 1] + 1;
                    }
                } else if (i < j) {
                    if (ch1 == ch2) {
                        // i和j匹配或不匹配
                        dp[i][j] = Math.min(dp[i - 1][j - 1], dp[i][j - 1] + 1);
                    } else {
                        // 增加s、替换
                        dp[i][j] = Math.min(dp[i][j - 1] + 1, dp[i - 1][j - 1] + 1);
                    }
                } else {
                    if (ch1 == ch2) {
                        dp[i][j] = Math.min(dp[i - 1][j - 1], dp[i - 1][j] + 1);
                    } else {
                        // 减小s、替换
                        dp[i][j] = Math.min(dp[i - 1][j] + 1, dp[i - 1][j - 1] + 1);
                    }
                }
            }
        }
        System.out.println(dp[n][m]);
    }
}