DDSA Solutions

3439. Reschedule Meetings for Maximum Free Time I

EasyView on LeetCode
ArrayGreedySorting
Time: O(n)
Space: O(n)

Problem Overview

Find maximum length increasing subsequence with constraint that adjacent pair differs by at most d.

Intuition

Find maximum length increasing subsequence with constraint that adjacent pair differs by at most d.

Algorithm

  1. 1DP: dp[i] = max LIS ending at i. Transition: dp[i] = 1 + max(dp[j]) where j < i, nums[j] < nums[i], nums[i]-nums[j] <= d.

Common Pitfalls

  • •Standard LIS DP with additional difference constraint. O(n^2) or segment tree for O(n log n).
3439.cs
C#
// Approach: Sliding window of k meetings; compute max gap after removing k consecutive meetings.
// Time: O(n) Space: O(n)

public class Solution
{
    public int MaxFreeTime(int eventTime, int k, int[] startTime, int[] endTime)
    {
        int[] gaps = GetGaps(eventTime, startTime, endTime);
        int windowSum = gaps.Take(k + 1).Sum();
        int ans = windowSum;

        for (int i = k + 1; i < gaps.Length; i++)
        {
            windowSum += gaps[i] - gaps[i - k - 1];
            ans = Math.Max(ans, windowSum);
        }

        return ans;
    }

    private int[] GetGaps(int eventTime, int[] startTime, int[] endTime)
    {
        int[] gaps = new int[startTime.Length + 1];
        gaps[0] = startTime[0];
        for (int i = 1; i < startTime.Length; ++i)
            gaps[i] = startTime[i] - endTime[i - 1];
        gaps[startTime.Length] = eventTime - endTime[endTime.Length - 1];
        
        return gaps;
    }
}
Was this solution helpful?

Related Problems