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
    }
}

package leetcode;

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

/**
 * https://leetcode.com/problems/heaters/
 */
public class Problem475 {
    public int findRadius(int[] houses, int[] heaters) {
        List<Element> list = new ArrayList<>();
        for (int house : houses) {
            list.add(new Element(house, false));
        }
        for (int heater : heaters) {
            list.add(new Element(heater, true));
        }
        Collections.sort(list, (a, b) -> {
            int cmp = Integer.compare(a.position, b.position);
            if (cmp == 0) {
                if (a.heater) {
                    return -1;
                } else {
                    return 1;
                }
            }
            return cmp;
        });
        int idx = 0;
        while (idx < list.size()) {
            if (list.get(idx).heater) {
                break;
            }
            idx++;
        }
        while (idx < list.size()) {
            Element heater = list.get(idx);
            int left = idx - 1;
            while (left >= 0 && !list.get(left).heater) {
                Element nonHeater = list.get(left);
                nonHeater.radius = Math.min(nonHeater.radius, Math.abs(heater.position - nonHeater.position));
                left--;
            }
            int right = idx + 1;
            while (right < list.size() && !list.get(right).heater) {
                Element nonHeater = list.get(right);
                nonHeater.radius = Math.min(nonHeater.radius, Math.abs(heater.position - nonHeater.position));
                right++;
            }
            idx = right;
        }
        int result = 0;
        for (Element e : list) {
            if (!e.heater) {
                result = Math.max(e.radius, result);
            }
        }
        return result;
    }

    private static class Element {
        private final int position;
        private final boolean heater;
        private int radius = Integer.MAX_VALUE;

        public Element(int position, boolean heater) {
            this.position = position;
            this.heater = heater;
        }

        @Override
        public String toString() {
            return "(" + position + ", " + heater + ", " + radius + ")";
        }
    }
}

Solve problem 475