|
1 | 1 | packagecom.fishercoder.solutions; |
2 | 2 |
|
3 | | -importcom.fishercoder.common.classes.Interval; |
4 | | - |
5 | | -importjava.util.Arrays; |
6 | | -importjava.util.Collections; |
7 | | -importjava.util.HashMap; |
8 | | -importjava.util.Map; |
| 3 | +importjava.util.TreeMap; |
9 | 4 |
|
10 | 5 | publicclass_436 { |
11 | 6 |
|
12 | 7 | publicstaticclassSolution1 { |
13 | | -publicint[]findRightInterval(Interval[]intervals) { |
14 | | -if (intervals ==null ||intervals.length ==0) { |
15 | | -returnnewint[0]; |
16 | | - } |
17 | | -int[]result =newint[intervals.length]; |
18 | | -result[0] = -1; |
19 | | -Intervallast =intervals[intervals.length -1]; |
20 | | -Intervalfirst =intervals[0]; |
21 | | -Map<Interval,Integer>map =newHashMap(); |
| 8 | +publicint[]findRightInterval(int[][]intervals) { |
| 9 | +TreeMap<Integer,Integer>map =newTreeMap<>(); |
| 10 | +int[]res =newint[intervals.length]; |
22 | 11 | for (inti =0;i <intervals.length;i++) { |
23 | | -map.put(intervals[i],i); |
24 | | - } |
25 | | - |
26 | | -Collections.sort(Arrays.asList(intervals), (o1,o2) ->o1.start -o2.start); |
27 | | - |
28 | | -for (inti =1;i <intervals.length;i++) { |
29 | | -//TODO: use binary search for the minimum start interval for interval[i-1] instead of a while loop |
30 | | -inttmp =i -1; |
31 | | -inttmpI =i; |
32 | | -while (tmpI <intervals.length &&intervals[tmpI].start <intervals[tmp].end) { |
33 | | -tmpI++; |
34 | | - } |
35 | | -if (tmpI <intervals.length) { |
36 | | -result[map.get(intervals[tmp])] =map.get(intervals[tmpI]); |
37 | | - }else { |
38 | | -result[map.get(intervals[tmp])] = -1; |
39 | | - } |
| 12 | +map.put(intervals[i][0],i); |
40 | 13 | } |
41 | | -if (result[intervals.length -1] ==0 &&last.end >first.start) { |
42 | | -result[intervals.length -1] = -1; |
| 14 | +for (inti =0;i <intervals.length;i++) { |
| 15 | +Integerkey =map.ceilingKey(intervals[i][intervals[i].length -1]); |
| 16 | +res[i] =key !=null ?map.get(key) : -1; |
43 | 17 | } |
44 | | -returnresult; |
| 18 | +returnres; |
45 | 19 | } |
46 | 20 | } |
47 | 21 |
|
|