Max free time after moving k events together #medium #sliding_window
Intuition
// .. ... .... ....
// .. ... .... .... ......
// a b c d
// a+b b+c c+d k=1
// a+b+c b+c+d k=2
// a+b+c+d k=3
Only the free intervals matter. Move k+1 intervals together with sliding window.
Approach
try to write O(1) memory solution
corner cases are start and the end
Complexity
Time complexity: $$O(n)$$
Space complexity: $$O(k)$$ or O(1)
Code
// 16ms
fun maxFreeTime(evt: Int, k: Int, st: IntArray, et: IntArray): Int {
val free = LinkedList<Int>(); var sum = 0
return (0..st.size).maxOf { i ->
val t = (if (i < st.size) st[i] else evt) - (if (i > 0) et[i - 1] else 0)
sum += t; free += t; if (free.size > k + 1) sum -= free.removeFirst()
sum
}
}
// 10ms
fun maxFreeTime(evt: Int, k: Int, st: IntArray, et: IntArray): Int {
var sum = 0
return (0..st.size).maxOf { i ->
sum += (if (i < st.size) st[i] else evt) - (if (i > 0) et[i - 1] else 0) -
(if (i > k) st[i - k - 1] else 0) + if (i - k - 2 >= 0) et[i - k - 2] else 0
sum
}
}
// 3ms
pub fn max_free_time(evt: i32, k: i32, st: Vec<i32>, et: Vec<i32>) -> i32 {
let (mut sum, k) = (0, k as usize);
(0..=st.len()).map(|i| {
sum += if i < st.len() { st[i] } else { evt } - if i > 0 { et[i - 1] } else { 0 } -
if i > k { st[i - k - 1] } else { 0 } + if i >= k + 2 { et[i - k - 2] } else { 0 };
sum
}).max().unwrap_or(0)
}
// 4ms
int maxFreeTime(int evt, int k, vector<int>& st, vector<int>& et) {
int sum = 0, res = 0, n = st.size();
for (int i = 0; i <= n; ++i) res = max(res, sum +=
(i < n ? st[i] : evt) -
(i > 0 ? et[i - 1] : 0) -
(i > k ? st[i - k - 1] : 0) +
(i >= k + 2 ? et[i - k - 2] : 0));
return res;
}
