Намерение состоит в том, чтобы выяснить все пары и получить максимальное совпадение из двух наборов в двудольном графе, скажем,
A = [(f1, g1), (f2, g2), ... upto m ]
B = [(x1, y1), (x2, y2), ... upto n ]
, где f, g, x и y - положительные целые числа. Между двумя наборами существует ребро, если выполняются оба условия 1 и 2.
1: f(i) > x(j)
2: g(i) <= y(j)
for any i <= m, j <= n
Итерации по каждой паре выполняются дольше при больших значениях m, n. Есть ли лучший алгоритм для определения всех возможных комбинаций?
Я пробовал следующее:
- Сортировать A по его признаку
x в обратном порядке - Brute итерация по B и A.
- Завершение внутреннего l oop по A, когда
f превышает x, удовлетворяющее условию 1, и вычисление условия 2 в пределах l oop.