Рубрики

Программа Python для задачи выбора активности | Жадный Алго-1

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

Example 1 : Consider the following 3 activities sorted
by finish time.
     start[]  =  {10, 12, 20};
     finish[] =  {20, 25, 30};
A person can perform at most two activities. The 
maximum set of activities that can be executed 
is {0, 2} [ These are indexes in start[] and 
finish[] ]

Example 2 : Consider the following 6 activities 
sorted by by finish time.
     start[]  =  {1, 3, 0, 5, 8, 5};
     finish[] =  {2, 4, 6, 7, 9, 9};
A person can perform at most four activities. The 
maximum set of activities that can be executed 
is {0, 1, 3, 4} [ These are indexes in start[] and 
finish[] ]

питон

«» «Следующая реализация предполагает, что деятельность
уже отсортированы по времени их окончания "" "

  
"" "Печатает максимальный набор действий, которые могут быть выполнены
один человек, по одному "" "
# n -> Общее количество действий
# s [] -> Массив, содержащий время начала всех действий
# f [] -> Массив, содержащий время окончания всех действий

  

def printMaxActivities(s, f ):

    n = len(f)

    print "The following activities are selected"

  

    # Первое действие всегда выбрано

    i = 0

    print i,

  

    # Рассмотрим остальные мероприятия

    for j in xrange(n):

  

        # Если время начала этого действия больше

        # или равно времени окончания ранее

        # выбранное занятие, затем выберите его

        if s[j] >= f[i]:

            print j,

            i = j

  
# Программа драйвера для проверки вышеуказанной функции

s = [1, 3, 0, 5, 8, 5]

f = [2, 4, 6, 7, 9, 9]

printMaxActivities(s, f)

  
# Этот код предоставлен Nikhil Kumar Singh

Выход:

The following activities are selected
0 1 3 4

Пожалуйста, обратитесь к полной статье о проблеме выбора деятельности | Жадный Алго-1 для более подробной информации!

Рекомендуемые посты:

Программа Python для задачи выбора активности | Жадный Алго-1

0.00 (0%) 0 votes