import java.util.Collections; import java.util.Scanner; import java.util.ArrayList; public class ISoar { Scanner in = new Scanner(System.in); ArrayList buildings; void start() { while (true) { float L = in.nextFloat(); // End-of-input condition if (L <= 0) return; // Input test case buildings = new ArrayList(); while (true) { float x1 = in.nextFloat(); float x2 = in.nextFloat(); // End-of-test case condition if (x1 > x2) break; buildings.add(new Building(x1, x2)); } // Sort buildings by increasing left endpoint Collections.sort(buildings); // Merge redundant intervals merge(); // Calculate uncovered distance for (int i = 0; i < buildings.size(); i++) { L -= buildings.get(i).dx; } // Print desired output System.out.printf("The total planting length is %.1f\n", L); } } void merge() { // List with only validated intervals ArrayList mergedList = new ArrayList(); // Initialize intervals to consider float left = buildings.get(0).xL; float right = buildings.get(0).xR; for (int i = 1; i < buildings.size(); i++) { float cur_left = buildings.get(i).xL; float cur_right = buildings.get(i).xR; // End condition for last interval considered if (i == buildings.size()-1) { mergedList.add(new Building(left, right)); break; } // Merge intervals if necessary if (cur_left <= left && cur_right > right) { right = cur_right; } // Otherwise, add verified interval to merged list else { mergedList.add(new Building(left, right)); left = cur_left; right = cur_right; } } // Replace original list with merged list buildings = mergedList; } // Class for each building class Building implements Comparable { // Left endpoint float xL; // Right endpoint float xR; // Length of building float dx; // Constructor Building(float a, float b) { xL = a; xR = b; dx = b - a; } // For sorting (will sort by increasing xL) public int compareTo(Building other) { float starts = this.xL - other.xL; if (starts > 0f) return 1; else if (starts < 0f) return -1; else return 0; } } public static void main(String[] args) { new ISoar().start(); } }