daily pastebin goal
3%
SHARE
TWEET

Untitled

a guest Mar 17th, 2018 63 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. public class Solution {
  2.     public int[] findRightInterval(Interval[] intervals) {
  3.         Map<Interval, Integer> map = new HashMap<>();
  4.         for (int i = 0; i < intervals.length; i++) {
  5.             map.put(intervals[i], i);
  6.         }
  7.         map.put(null, -1);
  8.         Arrays.sort(intervals, (a, b) -> a.start - b.start);
  9.         int[] indices = new int[intervals.length];
  10.         for (int i = 0; i < intervals.length; i++) {
  11.             indices[map.get(intervals[i])] = map.get(bsearch(intervals, i, intervals[i].end));
  12.         }
  13.         return indices;
  14.     }
  15.  
  16.     private Interval bsearch(Interval[] intervals, int i, int target) {
  17.         int l = i + 1;
  18.         int r = intervals.length;
  19.         while (l < r) {
  20.             int p = (l + r) >> 1;
  21.             if (intervals[p].start < target) {
  22.                 l = p + 1;
  23.             } else if (intervals[p - 1].start < target) {
  24.                 return intervals[p];
  25.             } else {
  26.                 r = p;
  27.             }
  28.         }
  29.         return null;
  30.     }
  31. }
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
 
Top