Reschedule Meetings for Maximum Free Time II | Leetcode 3440

class Solution {
    #define pii pair<int,int>
    int getFreeTimeByRescheduling(int& i,vector<pii>& top3,vector<int>& startTime, vector<int>& endTime){
        int last_end = i==0 ? 0 : endTime[i-1];
        if((top3[2].first >= endTime[i]-startTime[i]) and (top3[2].second!=i and top3[2].second!=i+1))
            return startTime[i+1]-last_end;
        else if((top3[1].first >= endTime[i]-startTime[i]) and (top3[1].second!=i and top3[1].second!=i+1))
            return startTime[i+1]-last_end;
        else if((top3[0].first >= endTime[i]-startTime[i]) and (top3[0].second!=i and top3[0].second!=i+1))
            return startTime[i+1]-last_end;

        return (startTime[i+1]-last_end)-(endTime[i]-startTime[i]);
    }
public:
    int maxFreeTime(int eventTime, vector<int>& startTime, vector<int>& endTime) {
        startTime.push_back(eventTime);
        endTime.push_back(eventTime);
        int n = startTime.size();
        
        //Precompute top3 gaps
        vector<pii> top3(3,{-1,-1});
        top3[0] = {startTime[0]-0,0};
        for(int i=1;i<n;++i){
            pii gap = {startTime[i]-endTime[i-1],i};
            if(gap.first > top3[2].first)       top3[2] = gap;
            if(top3[2].first > top3[1].first)   swap(top3[1],top3[2]);
            if(top3[1].first>top3[0].first)     swap(top3[0],top3[1]);     
        }
        //Parse left->right and reschedule each meeting
        int max_free_time = 0;
        for(int i=0;i<n-1;++i){
            int free_time = getFreeTimeByRescheduling(i,top3,startTime,endTime);
            max_free_time = max(max_free_time,free_time);
        }
        return max_free_time;
    }
};
/*
//JAVA
import java.util.*;

class Solution {
    static class Pair {
        int first;
        int second;
        Pair(int first, int second) {
            this.first = first;
            this.second = second;
        }
    }

    private int getFreeTimeByRescheduling(int i, List<Pair> top3, List<Integer> startTime, List<Integer> endTime) {
        int lastEnd = (i == 0) ? 0 : endTime.get(i - 1);
        int meetingDuration = endTime.get(i) - startTime.get(i);
        int nextStart = startTime.get(i + 1);
        int originalGap = nextStart - lastEnd;

        for (Pair gap : top3) {
            if (gap.first >= meetingDuration && gap.second != i && gap.second != i + 1) {
                return originalGap;
            }
        }

        return originalGap - meetingDuration;
    }

    public int maxFreeTime(int eventTime, List<Integer> startTime, List<Integer> endTime) {
        startTime.add(eventTime);
        endTime.add(eventTime);
        int n = startTime.size();

        // Precompute top 3 gaps
        List<Pair> top3 = new ArrayList<>();
        top3.add(new Pair(startTime.get(0) - 0, 0));
        top3.add(new Pair(-1, -1));
        top3.add(new Pair(-1, -1));

        for (int i = 1; i < n; i++) {
            Pair gap = new Pair(startTime.get(i) - endTime.get(i - 1), i);
            if (gap.first > top3.get(2).first) {
                top3.set(2, gap);
                Collections.sort(top3, (a, b) -> b.first - a.first);
            }
        }

        // Calculate maximum free time
        int maxFreeTime = 0;
        for (int i = 0; i < n - 1; i++) {
            int freeTime = getFreeTimeByRescheduling(i, top3, startTime, endTime);
            maxFreeTime = Math.max(maxFreeTime, freeTime);
        }

        return maxFreeTime;
    }
}

#Python
from typing import List

class Solution:
    def get_free_time_by_rescheduling(self, i: int, top3: List[tuple], start_time: List[int], end_time: List[int]) -> int:
        last_end = 0 if i == 0 else end_time[i - 1]
        meeting_duration = end_time[i] - start_time[i]
        next_start = start_time[i + 1]
        original_gap = next_start - last_end

        for gap in top3:
            if gap[0] >= meeting_duration and gap[1] != i and gap[1] != i + 1:
                return original_gap

        return original_gap - meeting_duration

    def max_free_time(self, event_time: int, start_time: List[int], end_time: List[int]) -> int:
        start_time.append(event_time)
        end_time.append(event_time)
        n = len(start_time)

        # Precompute top 3 gaps
        top3 = [(-1, -1), (-1, -1), (start_time[0] - 0, 0)]

        for i in range(1, n):
            gap = (start_time[i] - end_time[i - 1], i)
            if gap[0] > top3[2][0]:
                top3[2] = gap
                top3.sort(reverse=True, key=lambda x: x[0])

        # Calculate maximum free time
        max_free_time = 0
        for i in range(n - 1):
            free_time = self.get_free_time_by_rescheduling(i, top3, start_time, end_time)
            max_free_time = max(max_free_time, free_time)

        return max_free_time
*/