合并分区/压缩算法

Question

给定列表示例形式的硬盘的分区数(usedSpace及其totalSpace) usedSpace = 3,2,1,3,1 totalSpace = 3,5,3,5,5

这里，usedSpace是从该分区的总空间中使用的分区。

如果我们以最优的方式在分区周围移动数据，请找到保存所有数据所需的最小分区数。

在这种情况下，a)将数据从第1分区移动到第2分区，第1分区为空，b)将第3和第5分区的数据移动到第4分区，第3和第5分区将是免费的。

因此，只需要两个分区来保存所有数据。

Answer 1

因为移动的次数并不重要，而且由于数据可以被分割，贪婪的方法将起作用。伪码：

partitionCount := 0
# We're only worried about the total space used vs the total space available
unallocatedDataSize := sum of elements in usedSpace
# Greedily use the largest available space
sort totalSpace by size, descending
while unallocatedDataSize > 0 and totalSpace is not empty
  partitionSize := totalSpace.removeFirst()
  partitionCount := partitionCount + 1
  # Storing partitionSize data in this partition, remove it from our tracking
  unallocatedDataSize = unallocatedDataSize - partitionSize
return partitionCount

Answer 2

C#中的一种优化工作解决方案：

public int getMinDrives(int[] used, int[] total)
{
    int hdQty = 1;
    int pos = 0;
    int currentTotal;

    Array.Sort(total);
    Array.Reverse(total);
    int usedSum = used.Sum();

    while (usedSum > 0)
    {
        currentTotal = total[pos];
        usedSum = usedSum - currentTotal;

        if (usedSum > 0)
        {
            hdQty++;
            pos++;
            continue;
        }

    }

    return hdQty;
}

Answer 3

如果函数返回为整数值，其中包含每个分区上使用的空间数量和每个分区的总容量，那么这个问题如何通过Java来解决，比如：int minPartition(List<Integer> used, List<Integer> totalCapacity), --由贪婪方法提供的上述答案如何解析？

如果使用上面的代码，下面的代码会响应堆空间错误：

import java.util.ArrayList;
import java.util.List;

public class Program3 {

    public static void main(String[] args) {
        List<Integer> used = new ArrayList<>();

        List<Integer> totalCapacity = new ArrayList<>();

        used.add(1);
        used.add(2);
        used.add(3);

        totalCapacity.add(3);
        totalCapacity.add(3);
        totalCapacity.add(3);

        System.out.println(minPartitions(used,totalCapacity));


    }

    public static int minPartitions(List<Integer> used, List<Integer> totalCapacity) {
        // Write your code here
        int sizeOfUsedPartion = used.size();
        int sizeOfMemoryUsed = totalCapacity.size();
        List<Integer> newMemory = new ArrayList<>();
        while(sizeOfMemoryUsed != 0)
        {
            for(int i=0; i<sizeOfUsedPartion;i++)
            {
                for(int j=0; j<i;j++)
                {
                    if((used.get(i)+used.get(j)) <= totalCapacity.get(i))
                    {
                        newMemory.add((used.get(i)+used.get(j)));
                        break;
                    }
                }

            }
        }
        return newMemory.size();
    }
}