Advertisement
Guest User

Untitled

a guest
Jul 11th, 2018
83
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
Java 3.94 KB | None | 0 0
  1. import java.io.*;
  2. import java.util.*;
  3. import java.text.*;
  4. public class Intervals {
  5.     private static Set<Interval> retSet;
  6.     public static void main(String[] args) throws IOException {
  7.         BufferedReader br = new BufferedReader(new FileReader("/Users/abhinavdusi/Desktop/3.in"));
  8.         PrintWriter pw = new PrintWriter(new File("/Users/abhinavdusi/Desktop/3.out"));
  9.         String line;
  10.         while ((line = br.readLine()) != null) {
  11.             String[] data = line.split(" ");
  12.             double start = Double.parseDouble(data[0]), end = Double.parseDouble(data[1]);
  13.             int num = Integer.parseInt(br.readLine());
  14.             ArrayList<Interval> intervals = new ArrayList<>();
  15.             for (int i = 0; i < num; i ++) {
  16.                 data = br.readLine().split(" ");
  17.                 double dstart = Double.parseDouble(data[0]), dend = Double.parseDouble(data[1]);
  18.                 dstart = Math.max(dstart, start);
  19.                 dend = Math.min(dend, end);
  20.                 intervals.add(new Interval(dstart, dend));
  21.             }
  22.             Map<Interval, Integer> map = new HashMap<>();
  23.             for (int i = 0; i < intervals.size(); i ++) map.put(intervals.get(i), i);
  24.             Collections.sort(intervals, new SortByEnd());
  25.             double[] endTimes = new double[intervals.size()];
  26.             for (int i = 0; i < intervals.size(); i ++) endTimes[i] = intervals.get(i).end;
  27.             int result = num(start, end, intervals, endTimes);
  28.             if (result != -1) {
  29.                 pw.println(result);
  30.                 TreeSet<Integer> indicies = new TreeSet<>();
  31.                 for (Interval i : retSet) indicies.add(map.get(i));
  32.                 for (int i : indicies) pw.print(i + " ");
  33.                 pw.println();
  34.             } else pw.println("impossible");
  35.         }
  36.         br.close();
  37.         pw.close();
  38.         System.exit(0);
  39.     }
  40.     public static int num(double start, double end, ArrayList<Interval> intervals, double[] endTimes) {
  41.         DecimalFormat df = new DecimalFormat("##.000");
  42.         int n = intervals.size(), res = Integer.MAX_VALUE;
  43.         int[] dp = new int[n];
  44.         dp[0] = 1;
  45.         double[] values = new double[n];
  46.         Set[] intList = new Set[n];
  47.         for (int i = 0; i < intList.length; i ++) {
  48.             intList[i] = new HashSet<Interval>();
  49.             intList[i].add(intervals.get(i));
  50.         }
  51.         for (int i = 0; i < n; i ++) {
  52.             double thisStart = intervals.get(i).start, thisEnd = intervals.get(i).end;
  53.             int index = Arrays.binarySearch(endTimes, thisStart);
  54.             index = index <= -1 ? -index - 1 : index;
  55.             if (intervals.get(index).start >= thisStart) {
  56.                 dp[i] = dp[index];
  57.                 intList[i].addAll(intList[index]);
  58.                 if (i != index) intList[i].remove(intervals.get(index));
  59.                 values[i] = thisEnd - Math.min(thisStart, intervals.get(index).start);
  60.             } else {
  61.                 dp[i] = dp[index] + 1;
  62.                 intList[i].addAll(intList[index]);
  63.                 values[i] = values[index] + thisEnd - Math.max(intervals.get(index).end, thisStart);
  64.             }
  65.             values[i] = Double.parseDouble(df.format(values[i]));
  66.         }
  67.         double result = Double.parseDouble(df.format(end - start));
  68.         for (int i = 0; i < values.length; i ++)
  69.             if (values[i] == result && dp[i] < res) {
  70.                 res = dp[i];
  71.                 retSet = intList[i];
  72.             }
  73.         return res != Integer.MAX_VALUE ? res : -1;
  74.     }
  75. }
  76. class Interval {
  77.     public double start, end;
  78.     public Interval(double start, double end) {
  79.         this.start = start;
  80.         this.end = end;
  81.     }
  82. }
  83. class SortByEnd implements Comparator<Interval> {
  84.     public int compare(Interval a, Interval b) {
  85.         if (a.end > b.end) return 1;
  86.         else if (b.end < a.end) return -1;
  87.         else return a.start > b.start ? 1 : -1;
  88.     }
  89. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement