30ms JAVA nlogk solution similar to merge intervals


  • 2
    J

    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<>();
            for (int[] update : updates) list.add(update);
            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;
        }
    }

  • 0
    J

    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;
        }
    }

Log in to reply
 

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