BOJ. line Drawing (2170)

Problem: BOJ 2170 — Line Drawing · 한국어 · 日本語

Each of the N lines covers every point between its two endpoint coordinates. The task is to find the total length covered by at least one line. Sort the intervals by their left endpoint, then scan from left to right while keeping the rightmost endpoint of the current merged interval. If the next interval begins at or before that endpoint, it overlaps or touches the current interval, so extend the right endpoint only when necessary. If it begins later, add the completed interval’s length and start a new one. Touching intervals add no gap, and their combined length is the same either way.

Normalize each pair of endpoints so that left <= right. This also handles reversed endpoint input. A zero-length interval contributes no length. The final active interval must be added after the scan. The running total uses long so that coordinate differences and their sum do not overflow int.

Sorting costs O(N log N) and the scan costs O(N), for O(N log N) time overall. The interval list uses O(N) space.

Java

import java.io.BufferedInputStream;
import java.io.IOException;
import java.util.Arrays;

public class Main {
    static class FastScanner {
        private final BufferedInputStream input = new BufferedInputStream(System.in);
        private final byte[] buffer = new byte[1 << 16];
        private int position;
        private int limit;

        int nextInt() throws IOException {
            int c;
            do {
                c = read();
            } while (c <= ' ' && c != -1);

            int value = 0;
            int sign = 1;
            if (c == '-') {
                sign = -1;
                c = read();
            }
            while (c > ' ') {
                value = value * 10 + c - '0';
                c = read();
            }
            return value * sign;
        }

        private int read() throws IOException {
            if (position == limit) {
                limit = input.read(buffer);
                position = 0;
                if (limit == -1) return -1;
            }
            return buffer[position++];
        }
    }

    public static void main(String[] args) throws IOException {
        FastScanner input = new FastScanner();
        int n = input.nextInt();
        long[][] intervals = new long[n][2];

        for (int i = 0; i < n; i++) {
            long a = input.nextInt();
            long b = input.nextInt();
            intervals[i][0] = Math.min(a, b);
            intervals[i][1] = Math.max(a, b);
        }

        Arrays.sort(intervals, (a, b) -> Long.compare(a[0], b[0]));

        long left = intervals[0][0];
        long right = intervals[0][1];
        long totalLength = 0;
        for (int i = 1; i < n; i++) {
            long nextLeft = intervals[i][0];
            long nextRight = intervals[i][1];
            if (nextLeft <= right) {
                right = Math.max(right, nextRight);
            } else {
                totalLength += right - left;
                left = nextLeft;
                right = nextRight;
            }
        }
        totalLength += right - left;

        System.out.println(totalLength);
    }
}