package leetcode;

import java.util.Arrays;

/**
 * https://leetcode.com/problems/find-right-interval/
 */
public class Problem436 {
    public static class Interval {
        int start;
        int end;

        Interval() {
            start = 0;
            end = 0;
        }

        Interval(int s, int e) {
            start = s;
            end = e;
        }
    }

    public int[] findRightInterval(Interval[] intervals) {
        // TODO
        return new int[0];
    }

    public static void main(String[] args) {
        Problem436 prob = new Problem436();
        System.out.println(Arrays.toString(prob.findRightInterval(new Interval[]{
            new Interval(1, 2)
        }))); // [-1]
        System.out.println(Arrays.toString(prob.findRightInterval(new Interval[]{
            new Interval(3, 4),
            new Interval(2, 3),
            new Interval(1, 2)
        }))); // [-1, 0, 1]
        System.out.println(Arrays.toString(prob.findRightInterval(new Interval[]{
            new Interval(1, 4),
            new Interval(2, 3),
            new Interval(3, 4)
        }))); // [-1, 2, -1]
        System.out.println(Arrays.toString(prob.findRightInterval(new Interval[]{
            new Interval(4, 8),
            new Interval(3, 4),
            new Interval(1, 4)
        }))); // [-1, 0, 0]
        System.out.println(Arrays.toString(prob.findRightInterval(new Interval[]{
            new Interval(1, 2),
            new Interval(3, 5),
            new Interval(4, 5)
        }))); // [1, -1, -1]
    }
}

@@ -377,209 +377,127 @@
    p
-ublic int%5B%5D findRightInterval(Interval%5B%5D intervals) %7B%0A        // TODO%0A        return new int%5B0%5D
+rivate static class IntervalWrapper %7B%0A        private final int idx
 ;%0A    
-%7D%0A%0A
     p
-ublic static void main(String%5B%5D args) %7B%0A        Problem436 prob = new Problem436()
+rivate final Interval interval
 ;%0A
+%0A
         
 Syst
@@ -496,65 +496,48 @@
     
-System.out.println(Arrays.toString(prob.findRight
+public IntervalWrapper(int idx, 
 Interval
 (new
@@ -528,39 +528,35 @@
 dx, Interval
-(new I
+ i
 nterval
-%5B%5D
+) 
 %7B%0A          
@@ -557,34 +557,69 @@
         
-new I
+this.idx = idx;%0A            this.interval = i
 nterval
-(1, 2)
+;
 %0A       
@@ -624,69 +624,33 @@
    %7D
-))); // %5B-1%5D
 %0A    
+%7D%0A%0A
     
-System.out.println(Arrays.toString(prob.
+public int%5B%5D 
 find
@@ -655,36 +655,32 @@
 ndRightInterval(
-new 
 Interval%5B%5D%7B%0A    
@@ -677,73 +677,145 @@
 al%5B%5D
-%7B%0A            new Interval(3, 4),%0A            new Interval(2, 3),
+ intervals) %7B%0A        IntervalWrapper%5B%5D iws = new IntervalWrapper%5Bintervals.length%5D;%0A        for (int i = 0; i %3C intervals.length; i++) %7B
 %0A   
@@ -814,32 +814,41 @@
 +) %7B%0A           
+ iws%5Bi%5D =
  new Interval(1,
@@ -848,329 +848,393 @@
 rval
-(1, 2)%0A        %7D))); // %5B-1, 0, 1%5D%0A        System.out.println(Arrays.toString(prob.findRightInterval(new Interval%5B%5D%7B%0A            new Interval(1, 4),%0A            new Interval(2, 3),%0A            new Interval(3, 4)%0A        %7D))); // %5B-1, 2, -1%5D%0A        System.out.println(Arrays.toString(prob.findRightInterval(new Interval%5B%5D
+Wrapper(i, intervals%5Bi%5D);%0A        %7D%0A        Arrays.sort(iws, (a, b) -%3E Integer.compare(a.interval.start, b.interval.start));%0A        int%5B%5D result = new int%5Bintervals.length%5D;%0A        for (int i = 0; i %3C intervals.length; i++) %7B%0A            result%5Bi%5D = search(iws, intervals%5Bi%5D.end);%0A        %7D%0A        return result;%0A    %7D%0A%0A    private static int search(IntervalWrapper%5B%5D iws, int val) 
 %7B%0A  
@@ -1243,203 +1243,258 @@
     
-    new Interval(4, 8),%0A            new Interval(3, 4),%0A            new Interval(1, 4)%0A        %7D))); // %5B-1, 0, 0%5D%0A        System.out.println(Arrays.toString(prob.findRightInterval(new Interval%5B%5D
+int lo = 0;%0A        int hi = iws.length - 1;%0A        while (lo %3C= hi) %7B%0A            int mid = (lo + hi) / 2;%0A            if (iws%5Bmid%5D.interval.start == val) %7B%0A                return iws%5Bmid%5D.idx;%0A            %7D else if (iws%5Bmid%5D.interval.start %3E val) 
 %7B%0A  
@@ -1507,27 +1507,90 @@
     
-new Interval(1, 2),
+    hi = mid - 1;%0A            %7D else %7B%0A                lo = mid + 1;%0A            %7D
 %0A   
@@ -1598,91 +1598,112 @@
     
+%7D%0A
     
-new Interval(3, 5),%0A            new Interval(4, 5)%0A        %7D))); // %5B1, -1, -1%5D
+    if (lo %3E= iws.length %7C%7C hi %3C 0) %7B%0A            return -1;%0A        %7D%0A        return iws%5Blo%5D.idx;
 %0A   

Solve problem 436