Load Balancer

Introduction

You are given n servers each of which has a number of tasks. The goal is to have all n servers have the same number of tasks. In cases where the number of total tasks is not divisible by the number of servers, the number of tasks between any servers can have a maximum range of 1. You can move a single task from one server to another every second. Write a program that finds the minimum number of seconds before the servers are balanced.

Solution

Idea

The naive solution would be to move a single task from the most busy server to least busy server each second until the load is balanced. This solution does not finish in time (complexity is O(servers*tasks))

A better solution would be to calculate the average number of tasks (desired number of output tasks), and either add or remove tasks to/from a server. If the average rounds up, a number of servers (the "rounded" servers) have to add 1 to their tasks. If the average rounds down, a number of servers have to subtract 1 from their tasks. This ensures the correct answer in cases where the average number of tasks is not an integer. The number of seconds can then be calculated by adding together the difference between each servers' number of tasks and the rounded average. The answer is this number divided by 2 (because we need half the difference).

Runtime

Worst case runtime is O(servers).

Code

Solution - Java

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
import java.util.Scanner;

/**
 * Created by jiaweizhang on 2/8/2016.
 *
 * http://codeforces.com/problemset/problem/609/C
 */
public class LoadBalancer {
    public static void main(String args[]) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        List<Integer> tasks = new ArrayList<Integer>();
        for (int i=0; i<n; i++) {
            tasks.add(sc.nextInt());
        }

        long seconds = 0;
        Collections.sort(tasks);
        double average = calculateAverage(tasks);

        int sum = tasks.stream().mapToInt(Integer::intValue).sum();

        long roundedAvg = Math.round(average);

        if (Math.ceil(average)==Math.round(average)) {
            long num = Math.abs(sum - tasks.size() * roundedAvg);
            for (int i=0; i< num; i++) {
                tasks.set(i, tasks.get(i)+1);
            }

        } else if (Math.floor(average)==Math.round(average)) {
            long num = Math.abs(sum - tasks.size() * roundedAvg);
            for (int i=tasks.size()-1; i>= tasks.size()-num; i--) {
                tasks.set(i, tasks.get(i)-1);
            }
        }

        for (int i=0; i<tasks.size(); i++) {
            seconds = seconds + Math.abs(roundedAvg - tasks.get(i));
        }

        System.out.println(seconds/2);
    }

    private static double calculateAverage(List <Integer> marks) {
        Integer sum = 0;
        if(!marks.isEmpty()) {
            for (Integer mark : marks) {
                sum += mark;
            }
            return sum.doubleValue() / marks.size();
        }
        return sum;
    }
}