Алгоритм для сравнения элементов в двумерном массиве

Question

Я создаю программу Python для компании, которая продает аксессуары для iPhone. Программа будет иметь функцию, которая принимает в качестве параметра список списков, где каждый элемент списка содержит два значения, описывающих продукт - цену и оценочное качество (целочисленное значение). Я хотел бы найти случай, когда цена одного предмета ниже другого, но его качество выше, чем другое. Так, например, я передам этот список моей функции:

some_inventory = [[11.95, 10], [7.95, 12], [6.50, 3],...] 

В этом списке элемент [7,95, 12] будет иметь более низкую цену и высокое качество, чем [11,95, 10]. Если этот случай существует, я хотел бы вернуть логическое значение, например good_deal = True.

Существует около сотни тысяч элементов списка в some_inventory. Я могу использовать метод грубой силы, чтобы сравнить каждую цену со всеми другими ценами, а затем проверить их качество друг против друга, но это очень медленно. Сначала я попробовал сортировку по цене, а для предметов с одинаковой ценой я бы уничтожил предметы с более низким качеством и просто добавил элемент высшего качества в новый список (например, если были предметы с [4.50, 2], [4.50, 5] , [4.50, 8] Я добавил только [4.50, 8] в новый список). Но это все еще кажется слишком трудоемким.

Есть ли более эффективный алгоритм для этих сравнений? Это не должно быть в python, псевдокоде или C/C++ в порядке.

Answer 1

def has_good_deal(deals): 
    return sorted(deals) != sorted(deals, key=lambda x: list(reversed(x))) 

Левая часть выражения сортирует предложения по их цене, и если цены на них равны, по их качеству. Правая часть выражения сортирует сделки по их качеству, и если их качества равны по цене.

Если сортировки не равны, то существует как минимум две сделки [p1, q1] и [p2, q2], которые поменялись местами. Если они поменялись местами, p1<p2 и q1>q2, что означает, что [p1, q1] - это хорошая сделка по сравнению с [p2, q2]. Если сортировки равны, то нет хорошей сделки.