Meeting Rescheduling Challenge

Ninja is tasked with organizing a meeting in an office that starts at time ‘0’ and ends at time ‘LAST’. There are ‘N’ presentations scheduled with given start and end times. The presentations do not overlap. Your task is to help Ninja by rescheduling at most ‘K’ presentations while maintaining the original order, aiming to maximize the longest period without any scheduled presentation.

Explanation:

You are allowed to reschedule, but not alter the durations of, at most ‘K’ presentations to achieve the longest possible gap without presentations during the designated meeting time.

Example:

Input:

T = 1
N = 3, K = 1, LAST = 10
START = [0, 2, 5]
END = [1, 3, 6]

Output:

3

Constraints:

• 1 <= T <= 10
• 1 <= N <= 5000
• 0 <= K <= N
• 0 <= LAST <= 10^9
• START[i] < END[i], for 1 <= i <= N
• END[i] <= START[i+1], for 1 <= i < N

Note:

You do not need to print anything as it has already been handled. Simply implement the specified function to derive the solution.