Оптимизация решения проблемы «Простой балансировки нагрузки» в Codingame

Оптимизация решения проблемы «Простой балансировки нагрузки» в Codingame

Описание

В настоящее время я решаю проблему «Простой балансировки нагрузки» в Codingame, цель которой — распределить k задания между N серверами, чтобы минимизировать разницу между максимальной и минимальной нагрузкой.

Первоначальная настройка и текущий подход

import sys
import math

# Auto-generated code below aims at helping you parse
# the standard input according to the problem statement.

n = int(input())  # Number of servers
k = int(input())  # Number of jobs to distribute

# Read initial loads of servers
arr = []
for i in input().split():
    arr.append(int(i))

def load_diff(n, k, arr):
    arr.sort()
    while k > 0:
        arr[0] += 1
        k -= 1
        arr.sort()
    return arr[-1] - arr[0]

result = load_diff(n, k, arr)
print(result)

Текущий подход

• Сортировка: я сортирую список arr после каждого распределения заданий, чтобы поддерживать порядок, гарантируя, что в первую очередь регулируется наименьшая нагрузка на сервер.
• Увеличение нагрузки: я повторяю k раз, увеличивая нагрузку сервера с минимальной нагрузкой для распределения заданий.
• Окончательный расчет: после распределения всех работ я рассчитываю и распечатываю разницу между максимальной и минимальной нагрузкой.

Дополнительный контекст

• Проблема с производительностью: при выполнении всех тестовых случаев все проходят успешно, кроме тестового примера 4, в котором происходит тайм-аут (Le délai d'exécution du processus a été dépassé). Это говорит о том, что мое решение может быть недостаточно оптимизировано для эффективной обработки больших входных данных или конкретных крайних случаев.

• Ссылка на вызов: Простая балансировка нагрузки в Codingame

Что я пробовал и чего ожидал

Подход:

• Сортировка и распределение. Первоначально я сортировал список arr после каждого распределения заданий, чтобы поддерживать порядок и убедиться, что в первую очередь регулируется наименьшая нагрузка на сервер. Затем я повторил k раз, увеличивая нагрузку сервера с минимальной нагрузкой для распределения заданий.
• Ожидаемый результат: я ожидал, что этот подход позволит эффективно распределить задания между серверами, минимизируя при этом разницу между максимальной и минимальной нагрузкой.
• Фактический результат: хотя большинство тестовых случаев прошли успешно, в тестовом примере 4 произошел тайм-аут (Le délai d'exécution du processus a été dépassé), что указывает на то, что мое решение может быть недостаточно оптимизировано для больших входных данных или определенных крайних случаев.

Запрос руководства

Эта проблема является частью задачи по программированию на Codingame, и мне нужен совет по улучшению производительности и эффективности моего решения.

Любые предложения или помощь!