package leetcode;

/**
 * https://leetcode.com/problems/heaters/
 */
public class Problem475 {
    public int findRadius(int[] houses, int[] heaters) {
        // TODO
        return 0;
    }

    public static void main(String[] args) {
        Problem475 prob = new Problem475();
        System.out.println(prob.findRadius(new int[]{1, 2, 3}, new int[]{2})); // 1
        System.out.println(prob.findRadius(new int[]{1, 2, 3, 4}, new int[]{1, 4})); // 1
        System.out.println(prob.findRadius(new int[]{1, 2, 3, 4}, new int[]{1, 2})); // 2
        System.out.println(prob.findRadius(new int[]{1, 2, 3, 4}, new int[]{1, 2})); // 1
        System.out.println(prob.findRadius(new int[]{1, 2, 3}, new int[]{1})); // 2
        System.out.println(prob.findRadius(new int[]{1, 2, 3, 4, 5, 6}, new int[]{3})); // 3
        System.out.println(prob.findRadius(new int[]{1, 2, 6}, new int[]{1})); // 5
        System.out.println(prob.findRadius(new int[]{1, 6, 11}, new int[]{5, 12})); // 4
    }
}

@@ -12,16 +12,98 @@
 tcode;%0A%0A
+import java.util.ArrayList;%0Aimport java.util.Collections;%0Aimport java.util.List;%0A%0A
 /**%0A * h
@@ -239,213 +239,489 @@
     
-// TODO%0A        return 0;%0A
+List%3CElement%3E list = new ArrayList%3C%3E();%0A        for (int house : houses) %7B%0A   
     
-%7D%0A%0A
     
-public static void main(String%5B%5D args) %7B%0A        Problem475 prob = new Problem475();%0A        System.out.println(prob.findRadius(new int%5B%5D%7B1, 2, 3%7D, new int%5B%5D%7B2%7D)); //
+ list.add(new Element(house, false));%0A        %7D%0A        for (int heater : heaters) %7B%0A            list.add(new Element(heater, true));%0A        %7D%0A        Collections.sort(list, (a, b) -%3E %7B%0A            int cmp = Integer.compare(a.position, b.position);%0A            if (cmp == 0) %7B%0A                if (a.heater) %7B%0A                    return -1;%0A                %7D else %7B%0A                    return
  1
+;
 %0A   
@@ -729,619 +729,1566 @@
     
-System.out.println(prob.findRadius(new int%5B%5D%7B1, 2, 3, 4%7D, new int%5B%5D%7B1, 4%7D)); // 1%0A        System.out.println(prob.findRadius(new int%5B%5D%7B1, 2, 3, 4%7D, new int%5B%5D%7B1, 2%7D)); // 2%0A        System.out.println(prob.findRadius(new int%5B%5D%7B1, 2, 3, 4%7D, new int%5B%5D%7B1, 2%7D)); // 1%0A        System.out.println(prob.findRadius(new int%5B%5D%7B1, 2, 3%7D, new int%5B%5D%7B1%7D)); // 2%0A        System.out.println(prob.findRadius(new int%5B%5D%7B1, 2, 3, 4, 5, 6%7D, new int%5B%5D%7B3%7D)); // 3%0A        System.out.println(prob.findRadius(new int%5B%5D%7B1, 2, 6%7D, new int%5B%5D%7B1%7D)); // 5%0A        System.out.println(prob.findRadius(new int%5B%5D%7B1, 6, 11%7D, new int%5B%5D%7B5, 12%7D)); // 4
+        %7D%0A            %7D%0A            return cmp;%0A        %7D);%0A        int idx = 0;%0A        while (idx %3C list.size()) %7B%0A            if (list.get(idx).heater) %7B%0A                break;%0A            %7D%0A            idx++;%0A        %7D%0A        while (idx %3C list.size()) %7B%0A            Element heater = list.get(idx);%0A            int left = idx - 1;%0A            while (left %3E= 0 && !list.get(left).heater) %7B%0A                Element nonHeater = list.get(left);%0A                nonHeater.radius = Math.min(nonHeater.radius, Math.abs(heater.position - nonHeater.position));%0A                left--;%0A            %7D%0A            int right = idx + 1;%0A            while (right %3C list.size() && !list.get(right).heater) %7B%0A                Element nonHeater = list.get(right);%0A                nonHeater.radius = Math.min(nonHeater.radius, Math.abs(heater.position - nonHeater.position));%0A                right++;%0A            %7D%0A            idx = right;%0A        %7D%0A        int result = 0;%0A        for (Element e : list) %7B%0A            if (!e.heater) %7B%0A                result = Math.max(e.radius, result);%0A            %7D%0A        %7D%0A        return result;%0A    %7D%0A%0A    private static class Element %7B%0A        private final int position;%0A        private final boolean heater;%0A        private int radius = Integer.MAX_VALUE;%0A%0A        public Element(int position, boolean heater) %7B%0A            this.position = position;%0A            this.heater = heater;%0A        %7D%0A%0A        @Override%0A        public String toString() %7B%0A            return %22(%22 + position + %22, %22 + heater + %22, %22 + radius + %22)%22;%0A        %7D
 %0A   

Solve problem 475