Modified Find Right Interval.java

varunu28 · varunu28 · commit 38c6fa2c6ca6 · 2020-08-27T16:11:34.000-05:00
diff --git a/Medium/Find Right Interval.java b/Medium/Find Right Interval.java
@@ -1,42 +1,19 @@
-/**
- * Definition for an interval.
- * public class Interval {
- *     int start;
- *     int end;
- *     Interval() { start = 0; end = 0; }
- *     Interval(int s, int e) { start = s; end = e; }
- * }
- */
 class Solution {
-    public int[] findRightInterval(Interval[] intervals) {
-        int n = intervals.length;
-        if (n == 1) {
-            return new int[]{-1};
-        }
-
-        int[] start = new int[n];
-        Map<Integer, Integer> map = new HashMap<>();
-        for (int i=0; i<intervals.length; i++) {
-            start[i] = intervals[i].start;
-            map.put(intervals[i].start, i);
-        }
-
-        Arrays.sort(start);
-        int[] ans = new int[intervals.length];
-        for (int i=0; i<n; i++) {
-            int end = intervals[i].end;
-            int x = Arrays.binarySearch(start, end);
-            if (x > 0) {
-                ans[i] = map.get(end);
-            }
-            else if (-x > n) {
-                ans[i] = -1;
-            }
-            else {
-                ans[i] = map.get(start[-x-1]);
-            }
-        }
-
-        return ans;
+  public int[] findRightInterval(int[][] intervals) {
+    TreeMap<Integer, PriorityQueue<Integer>> map = new TreeMap<>();
+    for (int i = 0; i < intervals.length; i++) {
+      map.computeIfAbsent(intervals[i][0], k -> new PriorityQueue<>(
+          Comparator.comparingInt(o -> intervals[o][0]))
+      ).add(i);
     }
+    int[] ans = new int[intervals.length];
+    Arrays.fill(ans, -1);
+    for (int i = 0; i < intervals.length; i++) {
+      Integer upper = map.ceilingKey(intervals[i][1]);
+      if (upper != null) {
+        ans[i] = map.get(upper).peek();
+      }
+    }
+    return ans;
+  }
 }
