package sandbox;

import java.util.Arrays;

public class FindRange {

    class Range{
        int l;
        int r;

        public Range(int l, int r) {
            this.l = l;
            this.r = r;
        }
    }

    private Range[] ranges;

    // Initialization time complexity: O(NlogN), since we sort ranges
    public FindRange(String[] inputRanges) {
        int n = inputRanges.length;
        Range[] tmpRanges = new Range[n];

        for (int i = 0; i < n; i++) {
            // TODO: Extract as method
            String range = inputRanges[i];
            String[] rng = range.split("-");
            tmpRanges[i].l = Integer.valueOf(rng[0]);
            tmpRanges[i].r = Integer.valueOf(rng[1]);
        }

        // TODO Create a separate comparator
        // Time complexity: O(NlogN)
        Arrays.sort(tmpRanges, (a, b) -> a.l != b.l ? a.l - b.l : a.r - b.r);

        int count = 0;

        // Complexity: O(N)
        for (int i = 1; i < n; i++) {
            if (tmpRanges[count].r < tmpRanges[i].l) {
                // New range found
                count++;
            } else {
                // Merge ranges
                tmpRanges[count].r = tmpRanges[i].r;
            }
        }

        Range[] mergedRanges = new Range[count + 1];
        System.arraycopy(tmpRanges, 0, mergedRanges, 0, count + 1);

        this.ranges = mergedRanges;
    }

    // Time complexity: O(logN)
    // Find range using binary search in sorted ranges
    public boolean isInRanges(int v) {
        int l = 0;
        int r = ranges.length - 1;

        while (l <= r) {
            int mid = l + (r - l) / 2;

            if (ranges[mid].l >= v && v <= ranges[mid].r)
                return true;

            if (ranges[mid].l < v)
                r = mid - 1;
            else
                l = mid + 1;
        }

        return false;
    }
}