3635. Earliest Finish Time for Land and Water Rides II

class Solution {

    public int earliestFinishTime(int[] landStartTime, int[] landDuration,
                                  int[] waterStartTime, int[] waterDuration) {

        int ans1 = solve(landStartTime, landDuration,
                         waterStartTime, waterDuration);

        int ans2 = solve(waterStartTime, waterDuration,
                         landStartTime, landDuration);

        return Math.min(ans1, ans2);
    }

    private int solve(int[] firstStart, int[] firstDur,
                      int[] secondStart, int[] secondDur) {

        int m = secondStart.length;

        int[][] rides = new int[m][2];
        for (int i = 0; i < m; i++) {
            rides[i][0] = secondStart[i];
            rides[i][1] = secondDur[i];
        }

        Arrays.sort(rides, (a, b) -> Integer.compare(a[0], b[0]));

        int[] starts = new int[m];
        int[] prefixMinDur = new int[m];
        int[] suffixMinOpenFinish = new int[m];

        for (int i = 0; i < m; i++) {
            starts[i] = rides[i][0];
        }

        prefixMinDur[0] = rides[0][1];
        for (int i = 1; i < m; i++) {
            prefixMinDur[i] = Math.min(prefixMinDur[i - 1], rides[i][1]);
        }

        suffixMinOpenFinish[m - 1] = rides[m - 1][0] + rides[m - 1][1];
        for (int i = m - 2; i >= 0; i--) {
            suffixMinOpenFinish[i] = Math.min(
                suffixMinOpenFinish[i + 1],
                rides[i][0] + rides[i][1]
            );
        }

        int ans = Integer.MAX_VALUE;

        for (int i = 0; i < firstStart.length; i++) {

            int t = firstStart[i] + firstDur[i];

            int idx = lowerBound(starts, t);

            int best = Integer.MAX_VALUE;

            // rides with start >= t
            if (idx < m) {
                best = Math.min(best, suffixMinOpenFinish[idx]);
            }

            // rides with start < t
            if (idx > 0) {
                best = Math.min(best, t + prefixMinDur[idx - 1]);
            }

            ans = Math.min(ans, best);
        }

        return ans;
    }

    private int lowerBound(int[] arr, int target) {
        int l = 0, r = arr.length;

        while (l < r) {
            int mid = l + (r - l) / 2;

            if (arr[mid] < target) {
                l = mid + 1;
            } else {
                r = mid;
            }
        }

        return l;
    }
}

class Solution:
    def earliestFinishTime(self, landStartTime, landDuration,
                           waterStartTime, waterDuration):

        ans1 = self.solve(landStartTime, landDuration,
                          waterStartTime, waterDuration)

        ans2 = self.solve(waterStartTime, waterDuration,
                          landStartTime, landDuration)

        return min(ans1, ans2)

    def solve(self, firstStart, firstDur, secondStart, secondDur):

        rides = sorted(zip(secondStart, secondDur))

        m = len(rides)

        starts = [0] * m
        prefixMinDur = [0] * m
        suffixMinOpenFinish = [0] * m

        for i in range(m):
            starts[i] = rides[i][0]

        prefixMinDur[0] = rides[0][1]
        for i in range(1, m):
            prefixMinDur[i] = min(prefixMinDur[i - 1], rides[i][1])

        suffixMinOpenFinish[m - 1] = rides[m - 1][0] + rides[m - 1][1]
        for i in range(m - 2, -1, -1):
            suffixMinOpenFinish[i] = min(
                suffixMinOpenFinish[i + 1],
                rides[i][0] + rides[i][1]
            )

        ans = float("inf")

        for i in range(len(firstStart)):
            t = firstStart[i] + firstDur[i]

            idx = self.lowerBound(starts, t)

            best = float("inf")

            if idx < m:
                best = min(best, suffixMinOpenFinish[idx])

            if idx > 0:
                best = min(best, t + prefixMinDur[idx - 1])

            ans = min(ans, best)

        return ans

    def lowerBound(self, arr, target):
        l, r = 0, len(arr)

        while l < r:
            mid = l + (r - l) // 2

            if arr[mid] < target:
                l = mid + 1
            else:
                r = mid

        return l

class Solution {
public:
    int earliestFinishTime(vector<int>& landStartTime, vector<int>& landDuration,
                           vector<int>& waterStartTime, vector<int>& waterDuration) {

        int ans1 = solve(landStartTime, landDuration,
                         waterStartTime, waterDuration);

        int ans2 = solve(waterStartTime, waterDuration,
                         landStartTime, landDuration);

        return min(ans1, ans2);
    }

private:
    int solve(vector<int>& firstStart, vector<int>& firstDur,
              vector<int>& secondStart, vector<int>& secondDur) {

        int m = secondStart.size();

        vector<pair<int, int>> rides;
        for (int i = 0; i < m; i++) {
            rides.push_back({secondStart[i], secondDur[i]});
        }

        sort(rides.begin(), rides.end());

        vector<int> starts(m);
        vector<int> prefixMinDur(m);
        vector<int> suffixMinOpenFinish(m);

        for (int i = 0; i < m; i++) {
            starts[i] = rides[i].first;
        }

        prefixMinDur[0] = rides[0].second;
        for (int i = 1; i < m; i++) {
            prefixMinDur[i] = min(prefixMinDur[i - 1], rides[i].second);
        }

        suffixMinOpenFinish[m - 1] = rides[m - 1].first + rides[m - 1].second;
        for (int i = m - 2; i >= 0; i--) {
            suffixMinOpenFinish[i] = min(
                suffixMinOpenFinish[i + 1],
                rides[i].first + rides[i].second
            );
        }

        int ans = INT_MAX;

        for (int i = 0; i < firstStart.size(); i++) {

            int t = firstStart[i] + firstDur[i];

            int idx = lower_bound(starts.begin(), starts.end(), t) - starts.begin();

            int best = INT_MAX;

            if (idx < m) {
                best = min(best, suffixMinOpenFinish[idx]);
            }

            if (idx > 0) {
                best = min(best, t + prefixMinDur[idx - 1]);
            }

            ans = min(ans, best);
        }

        return ans;
    }
};

/**
 * @param {number[]} landStartTime
 * @param {number[]} landDuration
 * @param {number[]} waterStartTime
 * @param {number[]} waterDuration
 * @return {number}
 */
var earliestFinishTime = function (landStartTime, landDuration, waterStartTime, waterDuration) {

    const ans1 = solve(landStartTime, landDuration,
                       waterStartTime, waterDuration);

    const ans2 = solve(waterStartTime, waterDuration,
                       landStartTime, landDuration);

    return Math.min(ans1, ans2);
};

function solve(firstStart, firstDur, secondStart, secondDur) {

    const rides = [];

    for (let i = 0; i < secondStart.length; i++) {
        rides.push([secondStart[i], secondDur[i]]);
    }

    rides.sort((a, b) => a[0] - b[0]);

    const m = rides.length;

    const starts = new Array(m);
    const prefixMinDur = new Array(m);
    const suffixMinOpenFinish = new Array(m);

    for (let i = 0; i < m; i++) {
        starts[i] = rides[i][0];
    }

    prefixMinDur[0] = rides[0][1];
    for (let i = 1; i < m; i++) {
        prefixMinDur[i] = Math.min(prefixMinDur[i - 1], rides[i][1]);
    }

    suffixMinOpenFinish[m - 1] = rides[m - 1][0] + rides[m - 1][1];
    for (let i = m - 2; i >= 0; i--) {
        suffixMinOpenFinish[i] = Math.min(
            suffixMinOpenFinish[i + 1],
            rides[i][0] + rides[i][1]
        );
    }

    let ans = Number.MAX_SAFE_INTEGER;

    for (let i = 0; i < firstStart.length; i++) {

        const t = firstStart[i] + firstDur[i];

        const idx = lowerBound(starts, t);

        let best = Number.MAX_SAFE_INTEGER;

        if (idx < m) {
            best = Math.min(best, suffixMinOpenFinish[idx]);
        }

        if (idx > 0) {
            best = Math.min(best, t + prefixMinDur[idx - 1]);
        }

        ans = Math.min(ans, best);
    }

    return ans;
}

function lowerBound(arr, target) {

    let l = 0;
    let r = arr.length;

    while (l < r) {
        const mid = l + Math.floor((r - l) / 2);

        if (arr[mid] < target) {
            l = mid + 1;
        } else {
            r = mid;
        }
    }

    return l;
}