3270.求出数字答案

目标

给你三个 正 整数 num1 ,num2 和 num3 。

数字 num1 ,num2 和 num3 的数字答案 key 是一个四位数,定义如下:

  • 一开始,如果有数字 少于 四位数,给它补 前导 0 。
  • 答案 key 的第 i 个数位(1 <= i <= 4)为 num1 ,num2 和 num3 第 i 个数位中的 最小 值。

请你返回三个数字 没有 前导 0 的数字答案。

示例 1:

输入:num1 = 1, num2 = 10, num3 = 1000
输出:0
解释:
补前导 0 后,num1 变为 "0001" ,num2 变为 "0010" ,num3 保持不变,为 "1000" 。
数字答案 key 的第 1 个数位为 min(0, 0, 1) 。
数字答案 key 的第 2 个数位为 min(0, 0, 0) 。
数字答案 key 的第 3 个数位为 min(0, 1, 0) 。
数字答案 key 的第 4 个数位为 min(1, 0, 0) 。
所以数字答案为 "0000" ,也就是 0 。

示例 2:

输入: num1 = 987, num2 = 879, num3 = 798
输出:777

示例 3:

输入:num1 = 1, num2 = 2, num3 = 3
输出:1

说明:

  • 1 <= num1, num2, num3 <= 9999

思路

有三个小于等于 9999 的正整数,求四位数字 key,从左向右第 i 位是这三个数字对应数位(十进制)上数字的最小值。

根据题意模拟即可。

代码


/**
 * @date 2025-01-11 16:55
 */
public class GenerateKey3270 {
    public int generateKey(int num1, int num2, int num3) {
        int res = 0;
        int base = 1000;
        for (int i = 0; i < 4; i++) {
            int a1 = num1 / base;
            int a2 = num2 / base;
            int a3 = num3 / base;
            res += Math.min(a1, Math.min(a2, a3)) * base;
            num1 %= base;
            num2 %= base;
            num3 %= base;
            base /= 10;
        }
        return res;
    }
}

性能

3298.统计重新排列后包含另一个字符串的子字符串数目II

目标

给你两个字符串 word1 和 word2 。

如果一个字符串 x 重新排列后,word2 是重排字符串的 前缀,那么我们称字符串 x 是 合法的 。

请你返回 word1 中 合法 子字符串 的数目。

注意 ,这个问题中的内存限制比其他题目要 小 ,所以你 必须 实现一个线性复杂度的解法。

示例 1:

输入:word1 = "bcca", word2 = "abc"
输出:1
解释:
唯一合法的子字符串是 "bcca" ,可以重新排列得到 "abcc" ,"abc" 是它的前缀。

示例 2:

输入:word1 = "abcabc", word2 = "abc"
输出:10
解释:
除了长度为 1 和 2 的所有子字符串都是合法的。

示例 3:

输入:word1 = "abcabc", word2 = "aaabc"
输出:0

说明:

  • 1 <= word1.length <= 10^6
  • 1 <= word2.length <= 10^4
  • word1 和 word2 都只包含小写英文字母。

思路

参考 3297.统计重新排列后包含另一个字符串的子字符串数目I,本题内存限制小,必须使用线性复杂度的解法。

代码


/**
 * @date 2025-01-09 14:28
 */
public class ValidSubstringCount3297 {

    public long validSubstringCount_v1(String word1, String word2) {
        int[] cnt1 = new int[26];
        int[] cnt2 = new int[26];
        char[] chars1 = word1.toCharArray();
        char[] chars2 = word2.toCharArray();
        for (char c : chars1) {
            cnt1[c - 'a']++;
        }
        for (char c : chars2) {
            cnt2[c - 'a']++;
        }
        for (int i = 0; i < 26; i++) {
            if (cnt1[i] < cnt2[i]) {
                return 0;
            }
        }
        int n = word1.length();
        int r = n - 1;
        while (--cnt1[chars1[r] - 'a'] >= cnt2[chars1[r] - 'a']) {
            r--;
        }
        long res = n - r;
        cnt1[chars1[r++] - 'a']++;
        for (int i = 0; i < n - word2.length(); i++) {
            int c = chars1[i] - 'a';
            cnt1[c]--;
            while (r < n && cnt1[c] < cnt2[c]) {
                cnt1[chars1[r++] - 'a']++;
            }
            if (cnt1[c] >= cnt2[c]) {
                res += n - r + 1;
            } else {
                break;
            }
        }
        return res;
    }

}

性能

3297.统计重新排列后包含另一个字符串的子字符串数目I

目标

给你两个字符串 word1 和 word2 。

如果一个字符串 x 重新排列后,word2 是重排字符串的 前缀,那么我们称字符串 x 是 合法的 。

请你返回 word1 中 合法 子字符串 的数目。

示例 1:

输入:word1 = "bcca", word2 = "abc"
输出:1
解释:
唯一合法的子字符串是 "bcca" ,可以重新排列得到 "abcc" ,"abc" 是它的前缀。

示例 2:

输入:word1 = "abcabc", word2 = "abc"
输出:10
解释:
除了长度为 1 和 2 的所有子字符串都是合法的。

示例 3:

输入:word1 = "abcabc", word2 = "aaabc"
输出:0

说明:

  • 1 <= word1.length <= 10^5
  • 1 <= word2.length <= 10^4
  • word1 和 word2 都只包含小写英文字母。

思路

有两个字符串 word1word2,求 word1 有多个子字符串 满足子串的每个字符的出现次数 均大于等于 word2 中对应字符的出现次数。

暴力解法是枚举 word1 的每个子字符串,比较子串中的每个字符个数。具体来说就是统计 word1word2 中各字符的个数,枚举 word1 起点,从后向前枚举终点,如果某字符个数小于 word2 相应字符的个数则停止计数,继续下一个起点。这种解法的时间复杂度是 O(n^2) 会超时。

考虑使用滑动窗口,当左边元素移出窗口时,向右扩展,直到移出的元素个数达到 word2 中对应字符的个数,累加右边界到结尾的字符个数。

代码


/**
 * @date 2025-01-09 14:28
 */
public class ValidSubstringCount3297 {

    public long validSubstringCount_v1(String word1, String word2) {
        int[] cnt1 = new int[26];
        int[] cnt2 = new int[26];
        char[] chars1 = word1.toCharArray();
        char[] chars2 = word2.toCharArray();
        for (char c : chars1) {
            cnt1[c - 'a']++;
        }
        for (char c : chars2) {
            cnt2[c - 'a']++;
        }
        for (int i = 0; i < 26; i++) {
            if (cnt1[i] < cnt2[i]) {
                return 0;
            }
        }
        int n = word1.length();
        int r = n - 1;
        while (--cnt1[chars1[r] - 'a'] >= cnt2[chars1[r] - 'a']) {
            r--;
        }
        long res = n - r;
        cnt1[chars1[r++] - 'a']++;
        for (int i = 0; i < n - word2.length(); i++) {
            int c = chars1[i] - 'a';
            cnt1[c]--;
            while (r < n && cnt1[c] < cnt2[c]) {
                cnt1[chars1[r++] - 'a']++;
            }
            if (cnt1[c] >= cnt2[c]) {
                res += n - r + 1;
            } else {
                break;
            }
        }
        return res;
    }

}

性能

2264.字符串中最大的3位相同数字

目标

给你一个字符串 num ,表示一个大整数。如果一个整数满足下述所有条件,则认为该整数是一个 优质整数 :

  • 该整数是 num 的一个长度为 3 的 子字符串 。
  • 该整数由唯一一个数字重复 3 次组成。

以字符串形式返回 最大的优质整数 。如果不存在满足要求的整数,则返回一个空字符串 "" 。

注意:

  • 子字符串 是字符串中的一个连续字符序列。
  • num 或优质整数中可能存在 前导零 。

示例 1:

输入:num = "6777133339"
输出:"777"
解释:num 中存在两个优质整数:"777" 和 "333" 。
"777" 是最大的那个,所以返回 "777" 。

示例 2:

输入:num = "2300019"
输出:"000"
解释:"000" 是唯一一个优质整数。

示例 3:

输入:num = "42352338"
输出:""
解释:不存在长度为 3 且仅由一个唯一数字组成的整数。因此,不存在优质整数。

说明:

  • 3 <= num.length <= 1000
  • num 仅由数字(0 - 9)组成

思路

判断字符串中是否存在 三个连续相同的数字,如果有多个返回数字最大的那个。

可以使用一个变量记录连续相同的字符个数,如果不同就重置 cnt 为 1。

代码


/**
 * @date 2025-01-08 8:48
 */
public class LargestGoodInteger2264 {

    public String largestGoodInteger(String num) {
        char c = 0;
        int n = num.length();
        int cnt = 1;
        for (int i = 1; i < n; i++) {
            if (num.charAt(i) == num.charAt(i - 1)) {
                cnt++;
            } else {
                cnt = 1;
                continue;
            }
            if (cnt == 3 && c < num.charAt(i)) {
                c = num.charAt(i);
            }
        }
        return c > 0 ? new String(new char[]{c, c, c}) : "";
    }

}

性能

3019.按键变更的次数

目标

给你一个下标从 0 开始的字符串 s ,该字符串由用户输入。按键变更的定义是:使用与上次使用的按键不同的键。例如 s = "ab" 表示按键变更一次,而 s = "bBBb" 不存在按键变更。

返回用户输入过程中按键变更的次数。

注意:shift 或 caps lock 等修饰键不计入按键变更,也就是说,如果用户先输入字母 'a' 然后输入字母 'A' ,不算作按键变更。

示例 1:

输入:s = "aAbBcC"
输出:2
解释: 
从 s[0] = 'a' 到 s[1] = 'A',不存在按键变更,因为不计入 caps lock 或 shift 。
从 s[1] = 'A' 到 s[2] = 'b',按键变更。
从 s[2] = 'b' 到 s[3] = 'B',不存在按键变更,因为不计入 caps lock 或 shift 。
从 s[3] = 'B' 到 s[4] = 'c',按键变更。
从 s[4] = 'c' 到 s[5] = 'C',不存在按键变更,因为不计入 caps lock 或 shift 。

示例 2:

输入:s = "AaAaAaaA"
输出:0
解释: 不存在按键变更,因为这个过程中只按下字母 'a' 和 'A' ,不需要进行按键变更。

说明:

  • 1 <= s.length <= 100
  • s 仅由英文大写字母和小写字母组成。

思路

已知字符串 s,计算用户输入该字符串时按键的变更次数,不区分大小写。

根据题意比较相邻字符忽略大小写后是否相同,可以使用 |32 将字符都转为小写后比较。

代码


/**
 * @date 2025-01-07 8:46
 */
public class CountKeyChanges3019 {

    /**
     * A 65 010 00001 Z 90  010 11010
     * a 97 011 00001 Z 122 011 11010
     * 31   000 11111
     * 32   001 00000
     * 只有低 5 位不同,因此我们可以 &31 或者 |32
     */
    public int countKeyChanges_v1(String s) {
        int res = 0;
        int n = s.length();
        for (int i = 1; i < n; i++) {
            if ((s.charAt(i) | 32) != (s.charAt(i - 1) | 32)) {
                res++;
            }
        }
        return res;
    }

}

性能

2274.不含特殊楼层的最大连续楼层数

目标

Alice 管理着一家公司,并租用大楼的部分楼层作为办公空间。Alice 决定将一些楼层作为 特殊楼层 ,仅用于放松。

给你两个整数 bottom 和 top ,表示 Alice 租用了从 bottom 到 top(含 bottom 和 top 在内)的所有楼层。另给你一个整数数组 special ,其中 special[i] 表示 Alice 指定用于放松的特殊楼层。

返回不含特殊楼层的 最大 连续楼层数。

示例 1:

输入:bottom = 2, top = 9, special = [4,6]
输出:3
解释:下面列出的是不含特殊楼层的连续楼层范围:
- (2, 3) ,楼层数为 2 。
- (5, 5) ,楼层数为 1 。
- (7, 9) ,楼层数为 3 。
因此,返回最大连续楼层数 3 。

示例 2:

输入:bottom = 6, top = 8, special = [7,6,8]
输出:0
解释:每层楼都被规划为特殊楼层,所以返回 0 。

说明:

  • 1 <= special.length <= 10^5
  • 1 <= bottom <= special[i] <= top <= 10^9
  • special 中的所有值 互不相同

思路

给定一个区间 [bottom, top],从中剔除一些整数,求最大的连续整数个数。

排序 special 数组计算相邻区间的最大值。注意 special 数组的元素都在区间范围内,可以直接处理首尾区间 special[i] - bottomtop - special[i],然后再处理内部区间 special[i] - special[i - 1] - 1

也可以将 bottom--top++,然后统一处理。

代码


/**
 * @date 2025-01-06 8:42
 */
public class MaxConsecutive2274 {

    public int maxConsecutive(int bottom, int top, int[] special) {
        Arrays.sort(special);
        bottom--;
        top++;
        int res = 0;
        int n = special.length;
        int prev = bottom;
        for (int i = 0; i < n; i++) {
            res = Math.max(res, special[i] - prev - 1);
            prev = special[i];
        }
        return Math.max(res, top - special[n - 1] - 1);
    }

}

性能

2241.设计一个ATM机器

目标

一个 ATM 机器,存有 5 种面值的钞票:20 ,50 ,100 ,200 和 500 美元。初始时,ATM 机是空的。用户可以用它存或者取任意数目的钱。

取款时,机器会优先取 较大 数额的钱。

  • 比方说,你想取 $300 ,并且机器里有 2 张 $50 的钞票,1 张 $100 的钞票和1 张 $200 的钞票,那么机器会取出 $100 和 $200 的钞票。
  • 但是,如果你想取 $600 ,机器里有 3 张 $200 的钞票和1 张 $500 的钞票,那么取款请求会被拒绝,因为机器会先取出 $500 的钞票,然后无法取出剩余的 $100 。注意,因为有 $500 钞票的存在,机器 不能 取 $200 的钞票。

请你实现 ATM 类:

  • ATM() 初始化 ATM 对象。
  • void deposit(int[] banknotesCount) 分别存入 $20 ,$50,$100,$200 和 $500 钞票的数目。
  • int[] withdraw(int amount) 返回一个长度为 5 的数组,分别表示 $20 ,$50,$100 ,$200 和 $500 钞票的数目,并且更新 ATM 机里取款后钞票的剩余数量。如果无法取出指定数额的钱,请返回 [-1] (这种情况下 不 取出任何钞票)。

示例 1:

输入:
["ATM", "deposit", "withdraw", "deposit", "withdraw", "withdraw"]
[[], [[0,0,1,2,1]], [600], [[0,1,0,1,1]], [600], [550]]
输出:
[null, null, [0,0,1,0,1], null, [-1], [0,1,0,0,1]]
解释:
ATM atm = new ATM();
atm.deposit([0,0,1,2,1]); // 存入 1 张 $100 ,2 张 $200 和 1 张 $500 的钞票。
atm.withdraw(600);        // 返回 [0,0,1,0,1] 。机器返回 1 张 $100 和 1 张 $500 的钞票。机器里剩余钞票的数量为 [0,0,0,2,0] 。
atm.deposit([0,1,0,1,1]); // 存入 1 张 $50 ,1 张 $200 和 1 张 $500 的钞票。
                          // 机器中剩余钞票数量为 [0,1,0,3,1] 。
atm.withdraw(600);        // 返回 [-1] 。机器会尝试取出 $500 的钞票,然后无法得到剩余的 $100 ,所以取款请求会被拒绝。
                          // 由于请求被拒绝,机器中钞票的数量不会发生改变。
atm.withdraw(550);        // 返回 [0,1,0,0,1] ,机器会返回 1 张 $50 的钞票和 1 张 $500 的钞票。

说明:

  • banknotesCount.length == 5
  • 0 <= banknotesCount[i] <= 10^9
  • 1 <= amount <= 10^9
  • 总共 最多有 5000 次 withdraw 和 deposit 的调用。
  • 函数 withdraw 和 deposit 至少各有 一次 调用。

思路

设计一个ATM机,支持存入面额为 20,50,100,200,500 的钞票,取款时优先使用大额的钞票,即只要存在大额的钞票,不论最终能否凑成给定的数额,都要尽量多的取。如果无法取出指定数额的钱,返回 [-1],否则返回组合方案。

直接根据题意模拟即可,可以定义一个面额数组来避免硬编码。

代码


/**
 * @date 2025-01-05 15:10
 */
public class ATM {

    public int[] cnt = new int[5];
    public int[] value = new int[]{20, 50, 100, 200, 500};

    public ATM() {

    }

    public void deposit(int[] banknotesCount) {
        for (int i = 0; i < 5; i++) {
            cnt[i] += banknotesCount[i];
        }
    }

    public int[] withdraw(int amount) {
        int[] res = new int[5];
        for (int i = 4; i >= 0; i--) {
            res[i] = Math.min(amount / value[i], cnt[i]);
            amount -= res[i] * value[i];
        }
        if (amount == 0) {
            for (int i = 0; i < 5; i++) {
                cnt[i] -= res[i];
            }
            return res;
        } else {
            return new int[]{-1};
        }
    }
}

性能

732.我的日程安排表III

目标

当 k 个日程存在一些非空交集时(即, k 个日程包含了一些相同时间),就会产生 k 次预订。

给你一些日程安排 [startTime, endTime) ,请你在每个日程安排添加后,返回一个整数 k ,表示所有先前日程安排会产生的最大 k 次预订。

实现一个 MyCalendarThree 类来存放你的日程安排,你可以一直添加新的日程安排。

  • MyCalendarThree() 初始化对象。
  • int book(int startTime, int endTime) 返回一个整数 k ,表示日历中存在的 k 次预订的最大值。

示例:

输入:
["MyCalendarThree", "book", "book", "book", "book", "book", "book"]
[[], [10, 20], [50, 60], [10, 40], [5, 15], [5, 10], [25, 55]]
输出:
[null, 1, 1, 2, 3, 3, 3]
解释:
MyCalendarThree myCalendarThree = new MyCalendarThree();
myCalendarThree.book(10, 20); // 返回 1 ,第一个日程安排可以预订并且不存在相交,所以最大 k 次预订是 1 次预订。
myCalendarThree.book(50, 60); // 返回 1 ,第二个日程安排可以预订并且不存在相交,所以最大 k 次预订是 1 次预订。
myCalendarThree.book(10, 40); // 返回 2 ,第三个日程安排 [10, 40) 与第一个日程安排相交,所以最大 k 次预订是 2 次预订。
myCalendarThree.book(5, 15); // 返回 3 ,剩下的日程安排的最大 k 次预订是 3 次预订。
myCalendarThree.book(5, 10); // 返回 3
myCalendarThree.book(25, 55); // 返回 3

说明:

  • 0 <= startTime < endTime <= 10^9
  • 每个测试用例,调用 book 函数最多不超过 400次

思路

参考 731.我的日程安排表II,同样的思路,只不过求得是相交区间数量的最大值。

代码

/**
 * @date 2025-01-04 15:40
 */
public class MyCalendarThree {

    TreeMap<Integer, Integer> cnt = new TreeMap<>();

    public MyCalendarThree() {

    }

    public int book(int startTime, int endTime) {
        cnt.put(startTime, cnt.getOrDefault(startTime, 0) + 1);
        cnt.put(endTime, cnt.getOrDefault(endTime, 0) - 1);
        int res = 0;
        int appearanceCnt = 0;
        for (Map.Entry<Integer, Integer> entry : cnt.entrySet()) {
            int value = entry.getValue();
            appearanceCnt += value;
            res = Math.max(appearanceCnt, res);
        }
        return res;
    }
}

性能

731.我的日程安排表II

目标

实现一个程序来存放你的日程安排。如果要添加的时间内不会导致三重预订时,则可以存储这个新的日程安排。

当三个日程安排有一些时间上的交叉时(例如三个日程安排都在同一时间内),就会产生 三重预订。

事件能够用一对整数 startTime 和 endTime 表示,在一个半开区间的时间 [startTime, endTime) 上预定。实数 x 的范围为 startTime <= x < endTime。

实现 MyCalendarTwo 类:

  • MyCalendarTwo() 初始化日历对象。
  • boolean book(int startTime, int endTime) 如果可以将日程安排成功添加到日历中而不会导致三重预订,返回 true。否则,返回 false 并且不要将该日程安排添加到日历中。

示例 1:

输入:
["MyCalendarTwo", "book", "book", "book", "book", "book", "book"]
[[], [10, 20], [50, 60], [10, 40], [5, 15], [5, 10], [25, 55]]
输出:
[null, true, true, true, false, true, true]
解释:
MyCalendarTwo myCalendarTwo = new MyCalendarTwo();
myCalendarTwo.book(10, 20); // 返回 True,能够预定该日程。
myCalendarTwo.book(50, 60); // 返回 True,能够预定该日程。
myCalendarTwo.book(10, 40); // 返回 True,该日程能够被重复预定。
myCalendarTwo.book(5, 15);  // 返回 False,该日程导致了三重预定,所以不能预定。
myCalendarTwo.book(5, 10); // 返回 True,能够预定该日程,因为它不使用已经双重预订的时间 10。
myCalendarTwo.book(25, 55); // 返回 True,能够预定该日程,因为时间段 [25, 40) 将被第三个日程重复预定,时间段 [40, 50) 将被单独预定,而时间段 [50, 55) 将被第二个日程重复预定。

说明:

  • 0 <= start < end <= 10^9
  • 最多调用 book 1000 次。

思路

本题与 729.我的日程安排表I 的区别是允许相交一次。

使用差分数组记录区间元素被覆盖的次数,由于数据范围太大,这里使用 TreeMap 计数。

// todo 线段树

代码


/**
 * @date 2025-01-03 10:32
 */
public class MyCalendarTwo {

    TreeMap<Integer, Integer> cnt = new TreeMap<>();

    public MyCalendarTwo() {

    }

    public boolean book(int startTime, int endTime) {
        cnt.put(startTime, cnt.getOrDefault(startTime, 0) + 1);
        cnt.put(endTime, cnt.getOrDefault(endTime, 0) - 1);
        int appearanceCnt = 0;
        for (Map.Entry<Integer, Integer> entry : cnt.entrySet()) {
            int key = entry.getKey();
            int value = entry.getValue();
            if (key >= endTime) {
                break;
            }
            appearanceCnt += value;
            if (appearanceCnt > 2) {
                cnt.put(startTime, cnt.getOrDefault(startTime, 0) - 1);
                cnt.put(endTime, cnt.getOrDefault(endTime, 0) + 1);
                return false;
            }
        }
        return true;
    }
}

性能

729.我的日程安排表I

目标

实现一个 MyCalendar 类来存放你的日程安排。如果要添加的日程安排不会造成 重复预订 ,则可以存储这个新的日程安排。

当两个日程安排有一些时间上的交叉时(例如两个日程安排都在同一时间内),就会产生 重复预订 。

日程可以用一对整数 startTime 和 endTime 表示,这里的时间是半开区间,即 [startTime, endTime), 实数 x 的范围为, startTime <= x < endTime 。

实现 MyCalendar 类:

  • MyCalendar() 初始化日历对象。
  • boolean book(int startTime, int endTime) 如果可以将日程安排成功添加到日历中而不会导致重复预订,返回 true 。否则,返回 false 并且不要将该日程安排添加到日历中。

示例:

输入:
["MyCalendar", "book", "book", "book"]
[[], [10, 20], [15, 25], [20, 30]]
输出:
[null, true, false, true]
解释:
MyCalendar myCalendar = new MyCalendar();
myCalendar.book(10, 20); // return True
myCalendar.book(15, 25); // return False ,这个日程安排不能添加到日历中,因为时间 15 已经被另一个日程安排预订了。
myCalendar.book(20, 30); // return True ,这个日程安排可以添加到日历中,因为第一个日程安排预订的每个时间都小于 20 ,且不包含时间 20 。

说明:

  • 0 <= start < end <= 10^9
  • 每个测试用例,调用 book 方法的次数最多不超过 1000 次。

提示:

  • Store the events as a sorted list of intervals. If none of the events conflict, then the new event can be added.

思路

判断给定区间是否与已有区间相交,如果不相交将其加入已有区间。

最直接的想法是枚举每一个区间,判断是否相交,如果不相交则加入集合。判断区间 [a, b)[c, d) 是否相交,可以固定一个区间,然后让另一个区间滑动,可以发现相交需要满足 d > a && c < b,注意取等号是不相交的。

当然也可以使用二叉搜索树。

TreeSet 中查找特定元素的 API:

  • ceiling 返回的是 大于等于 target 的最小元素/ null
  • floor 返回的是 小于等于 target 的最大元素/ null
  • higher 返回的是 大于 target 的最小元素 / null
  • lower 返回的是 小于 target 的最大元素 / null

代码


/**
 * @date 2025-01-02 9:58
 */
class MyCalendar {

    TreeSet<int[]> ts = new TreeSet<>((a, b) -> a[0] - b[0]);

    public MyCalendar() {

    }

    public boolean book(int startTime, int endTime) {
        int[] interval = {startTime, endTime};
        if (ts.isEmpty()) {
            ts.add(interval);
            return true;
        }
        int[] param = new int[]{endTime, 0};
        // 查找 起点 大于等于 endTime 的 起点最小的区间,即要插入间隙的右边区间 right
        int[] right = ts.ceiling(param);
        // 如果 right 是第一个元素 或者 前面一个区间的右边界 end 小于等于 startTime,说明不相交
        if (right == ts.first() || ts.lower(param)[1] <= startTime) {
            ts.add(interval);
            return true;
        }
        return false;
    }

}

性能