4_collecting_signatures

4. Collecting Signatures

Problem Description

Task. Given a set of n segments {[a₀, b₀], [a₁, b₁], . . . , [a_n-1, b_n-1]} with integer coordinates on a line, find the minimum number m of points such that each segment contains at least one point. That is, find a set of integers X of the minimum size such that for any segment [a_i, b_i] there is a point x ∈ X such that a_i ≤ x ≤ b_i.

Input Format. The frst line of the input contains the number n of segments. Each of the following n lines contains two integers a_i and b_i (separated by a space) defining the coordinates of endpoints of the i-th segment.

Constraints. 1 ≤ n ≤ 100; 0 ≤ a_i ≤ b_i ≤ 10⁹ for all 0 ≤ i < n.

Output Format. Output the minimum number m of points on the first line and the integer coordinates of m points (separated by spaces) on the second line. You can output the points in any order. If there are many such sets of points, you can output any set. (It is not diffcult to see that there always exist a set of points of the minimum size such that all the coordinates of the points are integers.)

Sample 1.

    Input
        3
        1 3
        2 5
        3 6
    Output:
        13

Sample 2.

    Input
        4
        4 7
        1 3
        2 5
        5 6
    Output:
        2
        3 6

Solution

Algorithm

optimalPoints(segments[]):
    sort segments according to their endpoints
    length = segments.length
    points = []

    s = 1
    while s <= length:
        seg = segments[s]
        pointer = s
        while pointer <= length and segments[pointer].start <= seg.end
            increment pointer by 1
        add segment.end to the points list
        s = pointer

    return points

private static List<Integer> optimalPoints(Segment[] segments) {
    Arrays.sort(segments, new Comparator<Segment> () {
        public int compare(Segment s1, Segment s2) {
            if (s1.end < s2.end)
                return -1;
            else if (s1.end > s2.end) 
                return +1;
            else
                return 0;
        }
    });

    int n = segments.length;
    List<Integer> points = new ArrayList<Integer>();

    int s = 0;
    while (s < n) {
        Segment segment = segments[s];
        int p = s;
        while (p < n && segments[p].start <= segment.end) 
            p++;
        points.add(segment.end);
        s = p;
    }

    return points;
}

private static class Segment {
    int start, end;

    Segment(int start, int end) {
        this.start = start;
        this.end = end;
    }
}

Test

Compile with javac CoveringSegments.java and run with java CoveringSegments.

import java.util.*;

public class CoveringSegments {

    private static List<Integer> optimalPoints(Segment[] segments) {
        /* see previous code */
    }
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        Segment[] segments = new Segment[n];
        for (int i = 0; i < n; i++) {
            int start, end;
            start = scanner.nextInt();
            end = scanner.nextInt();
            segments[i] = new Segment(start, end);
        }
        List<Integer> points = optimalPoints(segments);
        System.out.println(points.size());
        for (int point : points) {
            System.out.print(point + " ");
        }
    }
}

This is only for discussion and communication. Please don't use this for submission of assignments.