GuilinDev

Lc0436

05 August 2008

436 Find Right Interval

原题

You are given an array of 

1

intervals
, where 
1

intervals[i] = [starti, endi]
and each 
1

starti
is unique.

The right interval for an interval 

1

i
is an interval 
1

j
such that 
1

startj >= endi
and 
1

startj
is minimized.

Return an array of right interval indices for each interval 

1

i
. If no right interval exists for interval 
1

i
, then put 
1

-1
at index 
1

i
.

Example 1:

1
2
3

Input: intervals = [[1,2]]
Output: [-1]
Explanation: There is only one interval in the collection, so it outputs -1.

Example 2:

1
2
3
4
5

Input: intervals = [[3,4],[2,3],[1,2]]
Output: [-1,0,1]
Explanation: There is no right interval for [3,4].
The right interval for [2,3] is [3,4] since start0 = 3 is the smallest start that is >= end1 = 3.
The right interval for [1,2] is [2,3] since start1 = 2 is the smallest start that is >= end2 = 2.

Example 3:

1
2
3
4

Input: intervals = [[1,4],[2,3],[3,4]]
Output: [-1,2,-1]
Explanation: There is no right interval for [1,4] and [3,4].
The right interval for [2,3] is [3,4] since start2 = 3 is the smallest start that is >= end1 = 3.

Constraints:

  • 1

    1 <= intervals.length <= 2 * 104

  • 1

    intervals[i].length == 2

  • 1

    -106 <= starti <= endi <= 106
  • The start point of each interval is unique.

分析

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

public class Solution {
    public int[] findRightInterval(Interval[] 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].start, i);    
        }
        
        for (int i = 0; i < intervals.length; ++i) {
            Map.Entry<Integer, Integer> entry = intervalMap.ceilingEntry(intervals[i].end);
            result[i] = (entry != null) ? entry.getValue() : -1;
        }
        
        return result;
    }
}
This site is open source. Improve this page.