Reschedule Meetings for Maximum Free Time I - Sliding Window - Constant Space [JS]

Description 

Solution: Sliding Window

Maintain a sliding window of size k + 2 and store the running sum of meetings within the window.
Within each window, move all meetings as left as possible or right as possible such that there is no space in between the meetings.
This maximizes the longest continuous gap.
This can be calculated by: last meeting start time - first meeting end time - sum of meeting durations in between first and last meetings.

Time Complexity: O(n)
Space Complexity: O(1)

JavaScript
function maxFreeTime(eventTime, k, startTime, endTime) {
  const n = startTime.length;
  let durationSum = 0, maxGap = 0;
  for (let i = 0; i < n; i++) {
    durationSum += endTime[i] - startTime[i];
    if (i >= k) {
      durationSum -= endTime[i - k] - startTime[i - k];
    }
    if (i >= k - 1) {
      const lastMeetingStart = i === n - 1 ? eventTime : startTime[i + 1];
      const firstMeetingEnd = i - k < 0 ? 0 : endTime[i - k];
      const gap = lastMeetingStart - firstMeetingEnd - durationSum;
      maxGap = Math.max(maxGap, gap);
    }
  }
  return maxGap;
};

Comments

Popular posts from this blog

Beautiful Towers II - Monotonic Increasing Stack [JS]

Check if There is a Valid Partition For The Array - Two Approaches - DP & Recursion w/ Memoization [JS]

Divide Nodes Into the Maximum Number of Groups - Union Find & BFS [JS]

Count Elements With Maximum Frequency - Hashmap [JS]

Robot Collisions - Stack [JS]