packagemedium;

importjava.util.ArrayList;

importjava.util.Arrays;

importjava.util.Collections;

importjava.util.Comparator;

importjava.util.HashMap;

importjava.util.List;

importjava.util.Map;

importutils.CommonUtils;

importclasses.Interval;

publicclassFindRightInterval {

publicstaticint[]findRightInterval(Interval[]intervals) {

if(intervals ==null ||intervals.length ==0)returnnewint[0];

int[]result =newint[intervals.length];

result[0] = -1;

Intervallast =intervals[intervals.length-1];

Intervalfirst =intervals[0];

Map<Interval,Integer>map =newHashMap();

for(inti =0;i <intervals.length;i++){

map.put(intervals[i],i);

}

Collections.sort(Arrays.asList(intervals),newComparator<Interval>(){

publicintcompare(Intervalo1,Intervalo2) {

returno1.start -o2.start;

}

});

for(inti =1;i <intervals.length;i++){

inttmp =i-1,tmpI =i;

while(tmpI <intervals.length &&intervals[tmpI].start <intervals[tmp].end)tmpI++;

if(tmpI <intervals.length)result[map.get(intervals[tmp])] =map.get(intervals[tmpI]);

elseresult[map.get(intervals[tmp])] = -1;

}

if(result[intervals.length-1] ==0 &&last.end >first.start)result[intervals.length-1] = -1;

returnresult;

}

publicstaticvoidmain(String...args){

Interval[]intervals =newInterval[3];

intervals[0] =newInterval(3,4);

intervals[1] =newInterval(2,3);

intervals[2] =newInterval(1,2);

findRightInterval(intervals);

}

}

|453|[Minimum Moves to Equal Array Elements](https://leetcode.com/problems/minimum-moves-to-equal-array-elements/)|[Solution](../../blob/master/EASY/src/easy/MinimumMovestoEqualArrayElements.java)| O(n)|O(1)| Easy|

|447|[Number of Boomerangs](https://leetcode.com/problems/number-of-boomerangs/)|[Solution](../../blob/master/EASY/src/easy/NumberofBoomerangs.java)| O(n^2)|O(n) | Easy| HashMap

|441|[Arranging Coins](https://leetcode.com/problems/arrange-coins/)|[Solution](../../blob/master/EASY/src/easy/ArrangingCoins.java)| O(n)|O(1)| Easy|

|436|[Find Right Interval](https://leetcode.com/problems/find-right-interval/)|[Solution](../../blob/master/MEDIUM/src/medium/FindRightInterval.java) | O(nlogn) |O(n) | Medium| Binary Search

|435|[Non-overlapping Intervals](https://leetcode.com/problems/non-overlapping-intervals/)|[Solution](../../blob/master/MEDIUM/src/medium/NonOverlappingIntervals.java) | O(nlogn) |O(1) | Medium| Greedy

|419|[Battleships in a Board](https://leetcode.com/problems/battleships-in-a-board/)|[Solution](../../blob/master/MEDIUM/src/medium/BattleshipsinaBoard.java) | O(n^2) |O(1) | Medium| DFS

|417|[Pacific Atlantic Water Flow](https://leetcode.com/problems/pacific-atlantic-water-flow/)|[Solution](../../blob/master/MEDIUM/src/medium/PacificAtlanticWaterFlow.java) | O(m*n*Max(m,n)) |O(m*n) | Medium| DFS