Как найти такой порядок списка, чтобы его элементы были больше, чем соответствующие элементы во втором списке. Я должен максимизировать такое количество

Question

Он не проходит один тестовый пример из 11.

Учитывая 2 списка, я должен найти порядок в 1-м списке, чтобы соответствующие элементы во втором списке имели меньшую величину.

Итак например: если в списке 1 есть элементы [10, 40, 30], а в списке 2 есть элементы [20,5,50] Здесь только 40 в списке 1 больше, чем соответствующее 5 в списке 2. Правильный порядок в списке 1 для максимального увеличения такого порядка будет [30,40,10], теперь 2 элемента больше соответствующих элементов в списке 2.

Обратите внимание, что должно быть строго больше.

Мой подход:

1. Итак я создал список кортежей, так что каждый кортеж представляет собой число из списка и список, к которому он принадлежит.
2. А затем я отсортировал этот список по числам в кортежах.
3. Перебираем список и каждую пару кортежей, если, скажем, элемент в списке 1 равен t1, а элемент в списке 2 - t2, тогда, если t1 встречается после t2, то у нас есть совпадение (поскольку это t1 будет больше th an t2, (я добавил случай, когда будет равенство, в этом случае он будет рассматривать просто как t1 = t2 и продолжать цикл).
4. Обновите параметры индекса и счетчик для успешного совпадения.

    def main(t1,t2):
        tn = []

        # Make a list of tuples such that each tuple is of the form (number, list it belongs to)
        # so if a number belongs to t1, say 5. So the tuple will look like (5,t1)

        for i,j in zip(t1,t2):
                tn.append((i,'t1'))
                tn.append((j,'t2'))

        # Sort this tuple on the basis of numbers
        tn = sorted(tn, key = lambda a: a[0]) 
        wins = 0

        t1_ind = 0
        t2_ind = 0

       # Implementation of point 3 from here
        while True:
            if t1_ind > t2_ind: # The t1 index should always be greater than t2 index for a match
                if tn[t2_ind][1] == 't2':

                    # An edge case for equal numbers, these won't be greater even if t1 occurs after t2

                    if tn[t1_ind][1] == 't1' and tn[t1_ind][0] != tn[t2_ind][0]: 
                        # We have a successful match here and hence we update the win count
                        wins += 1
                        t2_ind += 1  # Move t2's index ahead as we have a match
                    t1_ind += 1  # In any case if we find t2 and do an analysis, t1's index should move ahead
                else:
                   # if we don't find t2 and t2_index, then move ahead
                    t2_ind += 1
            else:
            # Update index of t1, as t1's index is <= t2's index now
                t1_ind += 1
            if t1_ind >= len(tn) - 1:
                break

        return wins

Это ошибка выдачи, и я не могу понять, что не так. Он проходит 10/11 тестовых случаев. В этом 1 крайнем случае ничего не показано, за исключением того факта, что на выполнение потребовалось 4 секунды и он завершился ошибкой

Это входит в O( n Log n). Если есть лучший подход или возможна оптимизация, я хотел бы знать.

Я нашел похожий пост, но он на C ++, и нет никаких объяснений, поэтому я не могу понять лог c . Аналогичная проблема в C ++

Изменить: некоторые дополнительные моменты о моем подходе, поскольку некоторые предполагают, что этот подход не является непосредственно интуитивным.

Для 2 списков алгоритм объединяет и сортирует их. После объединения и сортировки, например, порядок элементов:

1 3 4 5 5 6....

Итак, теперь мы сохраняем, какой элемент какому списку принадлежит: (l1 для списка 1 и l2 для списка2 )

l1 l2 l1 l1 l2 l1 ....

Теперь мы начинаем итерацию слева и ищем элементы l1 occurring after l2, числа, соответствующие l1, определенно будут больше, чем число, соответствующее наименее несогласованным l2, мы жадно составляем такие пары и увеличиваем счет для каждого совпадения, отмечая каждую совпавшую пару.

Answer 1

Sort both lists A and B (O(nlogn))

Make indices Aidx = 0, Bidx = 0

While A[Aidx] <= B[Bidx] increment Aidx

When A[Aidx] becomes larger than B[Bidx] - increment "wins" and increment both indices

Repeat until A end  (O(n) stage)

Код

import random
A = [random.randrange(1, 100) for _ in range(random.randrange(3, 10))]
B = [random.randrange(1, 100) for _ in range(random.randrange(3, 10))]
A.sort()
B.sort()
wins = 0
ia = 0
ib = 0
while ia < len(A) and ib < len(B):
    while ia < len(A) and A[ia] <= B[ib]:
        ia += 1
    if ia < len(A):
        wins += 1
        ia += 1
        ib += 1
print(A)
print(B)
print(wins)

[4, 5, 22, 30, 43, 55, 78, 80]
[19, 54, 85, 95]
2

[16, 17, 23, 26, 29, 34, 48, 98]
[6, 43, 65]
3