Блог

Я пытаюсь попрактиковаться в Google Kick Start и решить задачу сбора металла:

Вы отвечаете за развертывание роботов для сбора кикиума с близлежащего астероида. Роботы не предназначены для работы в команде, поэтому только один робот может собирать урожай в любой момент времени. Один робот может быть развернут в течение K единиц времени подряд, прежде чем он вернется для калибровки, независимо от того, сколько времени он тратит на сбор урожая в течение этого периода. Сбор урожая может выполняться только в течение определенных временных интервалов. Эти временные интервалы не перекрываются. Учитывая K и временные интервалы, в которые разрешен сбор урожая, какое минимальное количество развертываний роботов требуется для сбора урожая во все возможные моменты времени?

Я прочитал анализ и понял его, но я не понимаю, почему мое решение не работает. Я всегда получаю «WA» — неправильный ответ при его отправке.

Основная идея заключается в том, что я сначала сортирую интервалы, затем группирую их в блоки, где между всеми интервалами в блоке меньше K временных шагов. Затем внутри блока я непрерывно развертываю роботов каждые K шагов, т.Е. Требую math.ceil(chunk_len / K) роботов для каждого блока. Мне не нужны роботы между блоками.

Это имеет смысл концептуально, верно? Он также проходит мои тестовые примеры. Итак, я предполагаю, что у меня есть какая-то ошибка в отношении индексов списка или граничных случаев, но я не могу понять, что именно.

 import math


class Interval:
    def __init__(self, start, end):
        self.start = start
        self.end = end


class Solution:
    def __init__(self, max_time, intervals):
        self.max_time = max_time
        self.intervals = intervals

    def harvest_v1(self):
        """start harvesting and return min number of robots"""
        num_robots = 0

        # sort intervals with increasing start time --> O(N log(N))
        sorted_intervals = sorted(self.intervals, key=lambda interval: interval.start)

        # walk through intervals, starting at  --> O(N)
        chunk_start = sorted_intervals[0].start
        for i in range(1, len(sorted_intervals)):
            # calc duration to next interval and stop chunk if there's K or more time until the next interval
            time_to_next = sorted_intervals[i].start - sorted_intervals[i-1].end
            if time_to_next >= self.max_time:
                # then stop chunk and compute num robots needed for chunk
                chunk_len = sorted_intervals[i-1].end - chunk_start
                num_robots  = math.ceil(chunk_len / self.max_time)
                # start a new chunk
                chunk_start = sorted_intervals[i].start

        # then still include last interval
        chunk_len = sorted_intervals[-1].end - chunk_start
        num_robots  = math.ceil(chunk_len / self.max_time)

        return num_robots


# read input and generate output
num_tests = int(input())
for test in range(1, num_tests   1):
    num_intervals, max_time = [int(k) for k in input().split()]
    intervals = []
    for interval in range(num_intervals):
        start, end = [int(k) for k in input().split()]
        intervals.append(Interval(start, end))

    sol = Solution(max_time, intervals)
    print("Case #{}: {}".format(test, sol.harvest_v1()))
  

Любые советы будут оценены!

Ваш подход, вероятно, будет работать для большинства тестовых случаев, но есть несколько угловых случаев, которые докажут, что это неправильно. Попробуйте этот тестовый пример, вы поймете, почему он терпит неудачу:

     max_time = 6
    intervals = [Interval(1,3), Interval(4,7), Interval(11,16), Interval(17,22)]
  

Правильный вывод: 3

Результат вашей программы: 4

Объяснение

Ваш код помечает chunk start = start of the first interval и перематывает вперед, пока не найдет интервал с временным разрывом от предыдущего интервала >= max_time . Он вычисляет robot deployments требуемый до этого интервал, используя chunk start и end time текущего интервала в цикле. Поскольку ваш код обрабатывает только time_to_next >= self.max_time условие, его противоположное условие становится проблемой.

В тестовом примере, о котором я упоминал ранее, ваш код поместит все интервалы в один фрагмент, потому что временной разрыв между всеми интервалами меньше max_time , но оптимальным решением было бы сделать это в 2 или 3 фрагмента.

Если вы хотите попробовать другой подход, тогда взгляните на этот код:

 def harvest_v1(self):
    sorted_intervals = sorted(self.intervals, key=lambda interval: interval.start)
    robots_deployed = 0         # Keeps track of total robots deployed
    next_calibration_time = 0   # Keeps track of time for next robot calibration

    for interval in sorted_intervals:
        start_i = interval.start
        end_i = interval.end
        interval_duration = end_i - start_i

        if next_calibration_time <= start_i:    # If no robot has been deployed yet 
                                                # or previous robot has been sent for calibration, then
            
            # calculate the number of deployments required for current interval
            deployments_required = math.ceil(interval_duration / self.max_time)
            robots_deployed  = deployments_required

            # calculate and track the time at which lastly deployed robot will be sent for calibration
            next_calibration_time = start_i   (deployments_required * self.max_time)

        elif next_calibration_time < end_i:     # If some robot is still working then

            # calculate the time remaining in current interval after currently working robot becomes unavailable
            remaining_duration = end_i - next_calibration_time

            # calculate the number of deployments required
            deployments_required = math.ceil(remaining_duration / self.max_time)
            robots_deployed  = deployments_required

            # calculate and track the time at which lastly deployed robot will be sent for calibration
            next_calibration_time = next_calibration_time   (deployments_required * self.max_time)

    return robots_deployed