Interview-resourceConsumption

Problem Overview

The goal is to calculate the total resource consumption of tasks selected through a specific termination process in Amazon’s Elastic Container Service (ECS).

You are given an array resourceConsumption representing n tasks. You must repeat the following steps until no tasks remain:

• Identify the Target: Find the task with the lowest resource consumption value. If multiple tasks have the same minimum value, select the one with the smallest index.
• Record the Value: Add the value of this selected task to your running total.
• Remove Tasks: Remove the selected task and its immediate neighbors (the tasks directly to its left and right) from the array.
• Update Adjacency: After removal, the remaining tasks shift to become “adjacent” to each other (the gap closes).
• Return the final sum of all selected tasks’ resource consumption values.

Example: If you have $[4, 3, 2, 1]$, you pick 1 (the minimum). Its neighbor is 2. Both are removed, leaving $[4, 3]$. Next, you pick 3 (the new minimum), and its neighbor 4 is removed. $Total = 1 + 3 = 4$.

🧠 Summary of Thoughts

ArrayList

A crucial part of this code is the Right-to-Left removal sequence:

• Right Neighbor ($i+1$)
• Current Task ($i$)
• Left Neighbor ($i-1$)

By deleting the rightmost neighbor first, the code prevents “index shifting” from affecting the positions of the remaining tasks we intend to remove in the same cycle.

The use of ArrayList.remove() is clever here because it automatically shifts subsequent elements. This naturally “closes the gap”, making tasks that were previously separated become neighbors, which perfectly matches the problem’s requirements.

Doubly Linked List & Min-Priority Queue

The goal is to reduce the time complexity from $O(n^2) \rightarrow O(n \log n)$ by decoupling the “finding the minimum” step from the “removing elements” step. We use a Min-Priority Queue for efficient selection and a Doubly Linked List to maintain task adjacency in constant time (delete element).

✅ Code（Java）

import java.util.*;

class Result {
    public static int selectLeastResourceTasks(List<Integer> resourceConsumption) {
        // Convert to ArrayList so as to easier to remove elements
        List<Integer> tasks = new ArrayList<>(resourceConsumption);
        long totalResult = 0;

        while (!tasks.isEmpty()) {
            // Find the minimum value's index
            int minVal = tasks.get(0);
            int minIdx = 0;
            
            for (int i = 1; i < tasks.size(); i++) {
                if (tasks.get(i) < minVal) {
                    minVal = tasks.get(i);
                    minIdx = i;
                }
            }
            totalResult += minVal;

            // Remove elements: right -> medium -> left
            
            // Right
            if (minIdx + 1 < tasks.size()) {
                tasks.remove(minIdx + 1);
            }
            
            // current (medium)
            tasks.remove(minIdx);
            
            // Left
            if (minIdx - 1 >= 0) {
                tasks.remove(minIdx - 1);
            }
        }

        return (int) totalResult;
    }
}

import java.util.*;

// 1. 定义节点类，模拟双向链表中的一个任务
class Node {
    int val;
    int index;
    Node prev, next;
    boolean isRemoved = false; // 关键：标记该任务是否已被移除

    Node(int val, int index) {
        this.val = val;
        this.index = index;
    }
}

class Result {
    public static int selectLeastResourceTasks(List<Integer> resourceConsumption) {
        int n = resourceConsumption.size();
        if (n == 0) return 0;

        // 2. 准备最小堆 (PriorityQueue)
        // 排序规则：值小的优先；值相同，下标小的优先
        PriorityQueue<Node> minHeap = new PriorityQueue<>((a, b) -> {
            if (a.val != b.val) return Integer.compare(a.val, b.val);
            return Integer.compare(a.index, b.index);
        });

        // 3. 初始化所有节点并建立双向链表连接
        Node[] nodes = new Node[n];
        for (int i = 0; i < n; i++) {
            nodes[i] = new Node(resourceConsumption.get(i), i);
            minHeap.add(nodes[i]);
        }

        for (int i = 0; i < n; i++) {
            if (i > 0) nodes[i].prev = nodes[i - 1];
            if (i < n - 1) nodes[i].next = nodes[i + 1];
        }

        long totalConsumption = 0; // 用 long 防止溢出，最后转回 int

        // 4. 贪心模拟过程
        while (!minHeap.isEmpty()) {
            Node curr = minHeap.poll();

            // 如果这个节点已经被之前的邻居“连累”删除了，直接跳过
            if (curr.isRemoved) continue;

            // 选中当前最小值
            totalConsumption += curr.val;
            curr.isRemoved = true;

            // 处理逻辑上的“删除”：找到它的左右邻居
            Node left = curr.prev;
            Node right = curr.next;

            // 标记邻居为已移除
            if (left != null) left.isRemoved = true;
            if (right != null) right.isRemoved = true;

            // 5. 核心：更新双向链表的指向，让原本不相邻的节点在逻辑上相邻
            // 我们需要连接 left 的左边和 right 的右边
            Node newPrev = (left != null) ? left.prev : null;
            Node newNext = (right != null) ? right.next : null;

            if (newPrev != null) newPrev.next = newNext;
            if (newNext != null) newNext.prev = newPrev;
        }

        return (int) totalConsumption;
    }
}