# [Java] Abstract + Sort

• Same as other interval problem,

1. do one level abstraction,
2. sort them based on the index val, the start/falling type.
3. Scan through the sorted list. Here we use a stack as temporary storage.

TimeComplexity:
O(nlogn) Sorting + O(n)(Every node goes into stack and comes out of it at most once)

``````    public class Node implements Comparable<Node> {
int idx; // which interval it belongs too
int val;
int flag; // 0 equals end, 1 equals start;
public Node (int idx, int val, int flag) {
this.idx = idx;
this.val = val;
this.flag = flag;
}
@Override
public int compareTo(Node that){
if(this.val != that.val){
return this.val - that.val;
} else {
return this.flag - that.flag;
}
}

}
public int[] findRightInterval(Interval[] intervals) {
// One solution is to do one level abstraction
// Store the point along with its start,end, idx.
// Sort all the points.
if(intervals == null || intervals.length == 0) return null;
int len = intervals.length;
int[] res = new int[len];
Arrays.fill(res, -1);

//Iterate these the sorted point, if it's start point, pop whatever inside of stk and mark
// their next as current start point's idx
List<Node> nodes = new ArrayList<>();

int cnt = 0;
for(Interval itv : intervals) {
Node node1 = new Node(cnt, itv.start, 1);
Node node2 = new Node(cnt, itv.end, 0);
cnt++;
}

/*2nlog2n Time complexity*/
Collections.sort(nodes);

Stack<Integer> stk = new Stack<>();
for(Node node : nodes) {
if(node.flag == 0) {
stk.push(node.idx);
} else {
int start_idx = node.idx;
while(!stk.isEmpty()) {
int end_idx = stk.pop();
res[end_idx] = start_idx;
}
}
}

return res;
}
``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.