Count days without meetings

2021 年 7 月 3 日 星期六(已编辑)
/
18
摘要
题目要求计算没有会议的天数。解决方法是先将会议按开始时间排序,然后比较后一个会议的开始时间和前一个会议的结束时间,以确定是否有重叠或连续。时间复杂度为O(n),空间复杂度为O(1)。
这篇文章上次修改于 2025 年 7 月 12 日 星期六,可能部分内容已经不适用,如有疑问可询问作者。

Count days without meetings

Question

Analysis

  1. sort meetings array by start time of each meeting
  2. compare start time of latter and end time of former

Timing

21 min 14 sec

Code

public class Main1369 {
    public int countDays(int days, int[][] meetings) {
        Arrays.sort(meetings, Comparator.comparingInt(o -> o[0]));
        int hi = meetings[0][1];
        int res = meetings[0][0] - 1;
        for (int i = 1; i < meetings.length; i++) {
            int[] meeting = meetings[i];
            if (meeting[0] <= hi) {
                hi = Math.max(hi, meeting[1]);
            } else {
                res += (meeting[0] - hi - 1);
                hi = meeting[1];
            }
        }
        res += (days - hi);
        return res;
    }

    @Test
    public void test1() {
        int days = 10;
        int[][] meetings = {{5, 7}, {1, 3}, {9, 10}};
        int expected = 2; 
        assert countDays(days, meetings) == expected : "Test failed";
    }

    @Test
    public void test2() {
        int days = 5;
        int[][] meetings = {{2, 4}, {1, 3}};
        int expected = 1;
        assert countDays(days, meetings) == expected : "Test failed";
    }

    @Test
    public void test3() {
        int days = 6;
        int[][] meetings = {{1, 6}};
        int expected = 0;
        assert countDays(days, meetings) == expected : "Test failed";
    }
}

Complexity

Time O(nlog(n)) from sorting

Space O(log(n)) from sorting

使用社交账号登录

  • Loading...
  • Loading...
  • Loading...
  • Loading...
  • Loading...