436. Find Right Interval.md

436. Find Right Interval

---

leetcode Daily Challenge on August 27th, 2020.

---

Difficulty : Medium

Related Topics : BinarySearch

---

Given a set of intervals, for each of the interval i, check if there exists an interval j whose start point is bigger than or equal to the end point of the interval i, which can be called that j is on the "right" of i.

For any interval i, you need to store the minimum interval j's index, which means that the interval j has the minimum start point to build the "right" relationship for interval i. If the interval j doesn't exist, store -1 for the interval i. Finally, you need output the stored value of each interval as an array.

Note:

• You may assume the interval's end point is always bigger than its start point.
• You may assume none of these intervals have the same start point.

Example 1:

Input: [ [1,2] ]

Output: [-1]

Explanation: There is only one interval in the collection, so it outputs -1.

Example 2:

Input: [ [3,4], [2,3], [1,2] ]

Output: [-1, 0, 1]

Explanation: There is no satisfied "right" interval for [3,4].
For [2,3], the interval [3,4] has minimum-"right" start point;
For [1,2], the interval [2,3] has minimum-"right" start point.

Example 3:

Input: [ [1,4], [2,3], [3,4] ]

Output: [-1, 2, -1]

Explanation: There is no satisfied "right" interval for [1,4] and [3,4].
For [2,3], the interval [3,4] has minimum-"right" start point.

NOTE

• input types have been changed on April 15, 2019. Please reset to default code definition to get new method signature.

---

Solution

• mine
  • Java

    • Brute Force Runtime: 512 ms, faster than 8.10%, Memory Usage: 44.2 MB, less than 85.47% of Java online submissions

      //O(N^2)time
      //O(N)space
      public int[] findRightInterval(int[][] intervals) {
          int n = intervals.length;
          int[] s = new int[n];
          int[] e = new int[n];
          for(int i = 0; i < n; i++){
              s[i] = intervals[i][0];
              e[i] = intervals[i][1];
          }
          int[] res = new int[n];
          Arrays.fill(res, -1);
          for(int i = 0; i < n; i++){
              int t = -1;
              int min = Integer.MAX_VALUE;
              for(int j = 0; j < n;j++){
                  if(i !=j && s[j] >= e[i] && s[j] < min){
                      t = j;
                      min = s[j];
                  }
              }
              res[i] = t;
          }
          return res;
      }
      

    • BinarySearch Runtime: 9 ms, faster than 98.47%, Memory Usage: 48.2 MB, less than 45.11% of Java online submissions

      //O(N*logN)time
      //O(N)space
      public int[] findRightInterval(int[][] intervals) {
          int n = intervals.length;
          int[] res = new int[n];
          //because the start value is unique, save s and index in map
          HashMap<Integer, Integer> map = new HashMap<>();
          //save the start
          int[] s = new int[n];
          for (int i = 0; i < n; i++) {
              s[i] = intervals[i][0];
              map.put(s[i], i);
          }
          //sort the start arr
          Arrays.sort(s);
          for (int i = 0; i < n; i++) {
              res[i] = binarySearch(s, map, intervals[i][1]);
          }
          return res;
      }
      
      //binarysearch to get the first one who largger than v, and return the index in map
      int binarySearch(int[] s, HashMap<Integer, Integer> map, int v) {
          if (v <= s[0]) {
              return map.get(s[0]);
          } else if (v > s[s.length - 1]) {
              return -1;
          }
          int l = 0, r = s.length;
          while (l < r) {
              int mid = (l + r) >>> 1;
              if (s[mid] >= v) {
                  r = mid;
              } else {
                  l = mid + 1;
              }
          }
          return map.get(s[l]);
      }
      

---

• the most votes

• TreeMap Runtime: 20 ms, faster than 77.06%, Memory Usage: 47.4 MB, less than 58.41% of Java online submissions

  // O(N*logN)time
  // O(N)space
  public int[] findRightInterval(int[][] intervals) {
      int[] result = new int[intervals.length];
      java.util.NavigableMap<Integer, Integer> intervalMap = new TreeMap<>();
  
      for (int i = 0; i < intervals.length; ++i) {
          intervalMap.put(intervals[i][0], i);
      }
  
      for (int i = 0; i < intervals.length; ++i) {
          Map.Entry<Integer, Integer> entry = intervalMap.ceilingEntry(intervals[i][1]);
          result[i] = (entry != null) ? entry.getValue() : -1;
      }
  
      return result;
  }
  

---