BOJ. Water taxi (2836)

[Link] https://www.acmicpc.net/problem/2836 · 한국어 · 日本語

The taxi starts at position 0, must finish at position M, and can carry each passenger in either direction along the one-dimensional route. It first travels from 0 toward M. A passenger whose destination is to the right of their starting point can be dropped off as the taxi passes; serving such a trip adds no distance beyond the unavoidable M.

A passenger traveling left from start to destination (destination < start) is different. The taxi must leave its forward route to reach start, then return to the route at destination. This costs an extra 2 * (start - destination). Several left-going trips may share the same backtrack: on the route axis, each trip requires covering the interval [destination, start], and every point in the union of these intervals needs to be traveled backward and forward once. Thus, the answer is M + 2 * unionLength.

Sort only the left-going intervals by their left endpoint, then sweep them from left to right. If the next interval starts at or before the current interval’s right endpoint, the intervals overlap or touch and can be treated as one continuous interval. Otherwise, add the completed interval’s length and start a new one. The final accumulated union length is doubled and added to M. With no left-going passengers, the union is empty and the route length is simply M.

Sorting takes O(N log N) time and the sweep takes O(N) time. The algorithm uses O(N) space for the left-going intervals. Coordinates fit in int under the problem constraints, but the total distance is accumulated as long to avoid overflow.

Java

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Comparator;
import java.util.StringTokenizer;

public class Main {
    static class TripInterval {
        int left;
        int right;

        TripInterval(int left, int right) {
            this.left = left;
            this.right = right;
        }
    }

    public static void main(String[] args) throws IOException {
        BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer tokens = new StringTokenizer(reader.readLine());
        int passengerCount = Integer.parseInt(tokens.nextToken());
        long destination = Long.parseLong(tokens.nextToken());
        ArrayList<TripInterval> intervals = new ArrayList<>();

        for (int i = 0; i < passengerCount; i++) {
            tokens = new StringTokenizer(reader.readLine());
            int start = Integer.parseInt(tokens.nextToken());
            int end = Integer.parseInt(tokens.nextToken());
            if (end < start) intervals.add(new TripInterval(end, start));
        }

        intervals.sort(Comparator.comparingInt(interval -> interval.left));
        long extraDistance = 0;
        if (!intervals.isEmpty()) {
            int currentLeft = intervals.get(0).left;
            int currentRight = intervals.get(0).right;

            for (int i = 1; i < intervals.size(); i++) {
                TripInterval next = intervals.get(i);
                if (next.left <= currentRight) {
                    currentRight = Math.max(currentRight, next.right);
                } else {
                    extraDistance += (long) currentRight - currentLeft;
                    currentLeft = next.left;
                    currentRight = next.right;
                }
            }
            extraDistance += (long) currentRight - currentLeft;
        }

        System.out.println(destination + 2L * extraDistance);
    }
}