Count days without meetings
Question
Analysis
- sort meetings array by start time of each meeting
- 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