Insert an interval between an array of intervals

In this problem statement we have to insert a given interval between a given array of intervals. 

Insert Interval Leetcode

Approach:- Here we Insert the given interval in the array and then we use the same approach as we used in merge interval Leetcode question

 class Pair {

int x;

int y;

Pair(int x, int y) {

this.x = x;

this.y = y;

}

}

class Solution {

public int[][] insert(int[][] intervals, int[] newInterval) {

ArrayList<Pair> p = new ArrayList<>();

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

p.add(new Pair(intervals[i][0], intervals[i][1]));

}

p.add(new Pair(newInterval[0], newInterval[1]));

Collections.sort(p, (Pair a, Pair b) -> {

return a.x - b.x;

});

Stack<Pair> st = new Stack<>();

st.push(p.get(0));

for(int i=1;i<p.size();i++) {

Pair pp = st.pop();

if(p.get(i).x > pp.y) {

st.push(pp);

st.push(p.get(i));

} else {

int sm = pp.x;

int gt = Math.max(pp.y, p.get(i).y);

st.push(new Pair(sm, gt));

}

}

int[][] ans = new int[st.size()][2];

int y = st.size() - 1;

while(st.size() > 0) {

Pair pp = st.pop();

ans[y][0] = pp.x;

ans[y][1] = pp.y;

y--;

}

return ans;

}

}