HairCuts – SRM 261

HairCut.java

import java.util.Arrays;
import java.text.DecimalFormat;

public class HairCut {
    public static void main(String[] args){
        HairCut cut = new HairCut();

        double d;
        DecimalFormat f = new DecimalFormat("0.0########");

        System.out.println(f.format(cut.maxCut(new String[]{"04:22","09:00"},"05:52")));
        System.out.println(f.format(cut.maxCut(new String[]{"09:00","09:22","09:22"},"10:11")));
        System.out.println(f.format(cut.maxCut(new String[]{"09:00","04:00","04:02"},"04:09")));
        System.out.println(f.format(cut.maxCut(new String[]{"04:40", "10:54", "12:30", "03:46", "04:48", "01:57", "04:47", "10:29", "10:39"},"05:21")));

    }

    void getSortedMin(String[] a, int[] s){
        int i=0;
        for(String m: a){
            s[i++] = getMin(m);
        }
        Arrays.sort(s,0,s.length-1);
    }

    int getMin(String a){
        int h,m;
        String[] b = a.split(":",0);
        h = Integer.parseInt(b[0]);
        m = Integer.parseInt(b[1]);

        if(h<9) h=h+12;

        return (h-9)*60+m;
    }

    double maxCut(String[] enter, String lastExit){
        int lastExitMin = getMin(lastExit);
        int[] enterMin  = new int[enter.length+1];
        getSortedMin(enter,enterMin);
        enterMin[enter.length] = lastExitMin;

        double low,high;

        high=0;
        low=1<<30;
        for(int i=0;i<enterMin.length-1;i++){
            int t = enterMin[i+1]-enterMin[i];
            if(t<low) low=t;
            if(high<t) high=t;
        }

        while(low<high){
            System.out.printf("%f,%f -> ",low,high);
            double mid=low+(high-low)/2;
            double t=0.0;
            for(int m=0;m<enterMin.length-1;m++){
                if((double)enterMin[m]<t){
                    t=t+mid;
                }else{
                    t=(double)enterMin[m]+mid;
                }
            }

            System.out.printf("%f\n",t);
            if((double)lastExitMin<t) high=mid;
            else low=mid+0.0000000001;
        }

        if(low<5.0) low=-1.0;

        return low;
    }
}