We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
  1. Array Manipulation
  2. Discussions

Array Manipulation

  • trip2ken
     + 0 comments

    Java 8 - This solution does require a sort and then a full pass through the queries, but the memory overhead is less and still meet so the time requirments.

        public static long arrayManipulation(int n, List<List<Integer>> queries) {
        long result = Integer.MIN_VALUE;
        
        queries.sort((q1,q2)->Integer.compare(q1.get(0), q2.get(0)));
        
        PriorityQueue<List<Integer>> expireQueue = new PriorityQueue<>(
            (q1,q2)->Integer.compare(q1.get(1), q2.get(1))
        ) ;
        long runningTotal = 0;
        
        for (List<Integer> query: queries) {
            int idx = query.get(0);            
            expireQueue.offer(query);
            
            runningTotal += query.get(2);
            
            while(expireQueue.peek().get(1)<idx) 
                runningTotal -= expireQueue.poll().get(2) ;
            
            if (runningTotal>result)
                result = runningTotal;
        }
        return result ;
    }