LEETCODE 1229. Meeting Scheduler 解题思路分析

题目大意:

安排会议日程

你是一名行政助理,手里有两位客户的空闲时间表:slots1 和 slots2,以及会议的预计持续时间 duration,请你为他们安排合适的会议时间。

「会议时间」是两位客户都有空参加,并且持续时间能够满足预计时间 duration 的 最早的时间间隔。

如果没有满足要求的会议时间,就请返回一个 空数组。

「空闲时间」的格式是 [start, end],由开始时间 start 和结束时间 end 组成,表示从 start 开始,到 end 结束。

题目保证数据有效:同一个人的空闲时间不会出现交叠的情况,也就是说,对于同一个人的两个空闲时间 [start1, end1] 和 [start2, end2],要么 start1 > end2,要么 start2 > end1。

示例 1:

输入:
 slots1 = [[10,50],[60,120],[140,210]],
 slots2 = [[0,15],[60,70]],
 duration = 8
输出:[60,68]

示例 2:

输入:
 slots1 = [[10,50],[60,120],[140,210]],
 slots2 = [[0,15],[60,70]],
 duration = 12
输出:[]

提示:

  • 1 <= slots1.length, slots2.length <= 10^4
  • slots1[i].length, slots2[i].length == 2
  • slots1[i][0] < slots1[i][1]
  • slots2[i][0] < slots2[i][1]
  • 0 <= slots1[i][j], slots2[i][j] <= 10^9
  • 1 <= duration <= 10^6

如果想查看本题目是哪家公司的面试题,请参考以下免费链接: https://leetcode.jp/problemdetail.php?id=1229

解题思路分析:

解这道题目之前应该先对两个数组按照起始时间进行升序排序。排序后,从两个数组的第0位开始比较,比较结果会有以下几种情况:

  1. 客户1与客户2的空闲时间区间为包含关系时,子集部分为两者共同空闲时间,如果子集的时间长度大于等于duration,那么子集的开始时刻到加上duration的区间为解,反之,子集所代表的的一方index加一,继续比较。
  2. 客户1与客户2的空闲时间区间是部分交集关系,那么要看交集的部分是否大于等于duration,如果是,那么交集的起点到加上duration的区间为解,如果否,结束时间较早的一方index加一,继续比较。
  3. 当客户1与客户2的空闲时间区间没有交集时,结束时间较早的一方index加一,继续比较。

当循环结束后,没有在上述三种三种情况中找到解,返回空List即可。

实现代码:

public List<Integer> minAvailableDuration(int[][] slots1, int[][] slots2, int duration) {
    Comparator c = new Comparator<int[]>() { // 按照开始时间排序
        @Override
        public int compare(int[] o1, int[] o2) {
            return o1[0]-o2[0];
        }
    };
    Arrays.sort(slots1, c); // 排序slots1
    Arrays.sort(slots2, c); // 排序slots2
    int i1=0, i2=0; // 起始时,客户1和客户2的下标均为0
    while(i1<slots1.length && i2<slots2.length){
        // 客户1的结束时间小于客户2的开始时间,两者不相交
        if(slots1[i1][1]<slots2[i2][0]){
            i1++; // 客户1的index加一
        }
        // 客户2的结束时间小于客户1的开始时间,两者不相交
        else if(slots2[i2][1]<slots1[i1][0]){
            i2++; // 客户2的index加一
        }
        // 客户2是客户1的子集
        else if(slots1[i1][0]<=slots2[i2][0]
         &&slots1[i1][1]>=slots2[i2][1]){
            // 当客户2的时间区间长度大于等于duration
            if(slots2[i2][1]-slots2[i2][0]>=duration){
                // 返回合理区间
                return getList(slots2[i2][0], duration);
            }
            i2++; // 客户2的index加一
        }
        // 客户1是客户2的子集
        else if(slots2[i2][0]<=slots1[i1][0]
         &&slots2[i2][1]>=slots1[i1][1]){
            // 当客户1的时间区间长度大于等于duration
            if(slots1[i1][1]-slots1[i1][0]>=duration){
                // 返回合理区间
                return getList(slots1[i1][0], duration);
            }
            i1++; // 客户1的index加一
        }
        // 客户1和客户2有部分交集(客户2在前)
        else if(slots2[i2][1]>=slots1[i1][0]
         &&slots2[i2][0]<slots1[i1][0]){
            if(slots2[i2][1]-slots1[i1][0]>=duration){
                return getList(slots1[i1][0], duration);
            }
            i2++;
        }
        // 客户1和客户2有部分交集(客户1在前)
        else if(slots1[i1][1]>=slots2[i2][0]
         &&slots1[i1][0]<slots2[i2][0]){
            if(slots1[i1][1]-slots2[i2][0]>=duration){
                return getList(slots2[i2][0], duration);
            }
            i1++;
        }
    }
    return new ArrayList<>();
}
List<Integer> getList(int start, int duration){
    List<Integer> res = new ArrayList<>();
    res.add(start);
    res.add(start+duration);
    return res;
}

本题解法执行时间为31ms。

Runtime: 31 ms, faster than 92.68% of Java online submissions for Meeting Scheduler.

Memory Usage: 48.2 MB, less than 100.00% of Java online submissions for Meeting Scheduler.

本网站文章均为原创内容,并可随意转载,但请标明本文链接
如有任何疑问可在文章底部留言。为了防止恶意评论,本博客现已开启留言审核功能。但是博主会在后台第一时间看到您的留言,并会在第一时间对您的留言进行回复!欢迎交流!
本文链接: http://leetcode.jp/leetcode-1229-meeting-scheduler-解题思路分析/
此条目发表在leetcode分类目录,贴了, , , 标签。将固定链接加入收藏夹。

发表评论

您的电子邮箱地址不会被公开。