# 30ms JAVA nlogk solution similar to merge intervals

• Sort the intervals with start first, use a heap (use end as compare) to maintain current valid intervals while iterating the result array.

``````public class Solution {
public int[] getModifiedArray(int length, int[][] updates) {
int[] res = new int[length];
List<int[]> list = new ArrayList<>();
Collections.sort(list, new Comparator<int[]>() {
@Override
public int compare(int[] a, int[] b) {
return a[0] - b[0];
}
});

PriorityQueue<int[]> q = new PriorityQueue<int[]>(10, new Comparator<int[]>() {
@Override
public int compare(int[] a, int[] b) {
return a[1] - b[1];
}
});

int index = 0, sum = 0;
for (int i = 0; i < length; i++) {
while (index < list.size() && list.get(index)[0] == i) {
sum += list.get(index)[2];
q.offer(list.get(index++));
}
while (!q.isEmpty() && q.peek()[1] < i) {
sum -= q.poll()[2];
}
res[i] = sum;
}
return res;
}
}``````

• wow, so smart, you guys also have a O(m + k) solution:

``````public class Solution {
public int[] getModifiedArray(int length, int[][] updates) {
int[] arr = new int[length];
for (int[] update : updates) {
arr[update[0]] += update[2];
if (update[1] != length - 1) arr[update[1] + 1] -= update[2];
}
for (int i = 1; i < length; i++) arr[i] += arr[i - 1];
return arr;
}
}``````

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