Алгоритмы поиска и сортировки на python

[Nicodim]

Здравствуйте, помогите пожалуйста найти ошибку в коде. В последней строке выводит 2 6 5, а нужно
2 3 5.

Задача.

У пастуха есть n псов и m овец, причём i-й пёс характеризуется числом bi , а j-я овца характеризуется числом aj.

Пастух хочет отправить овец гулять под надзором псов. Овцу можно выпустить гулять только вместе с двумя псами-надсмотрщиками, причём если выбрана i-я овца вместе с j-м и k-м псами, то должны выполняться неравенства:
bj<ai<bk.

Помогите пастуху выбрать наибольшее количество овец, которых можно отправить на прогулку за один раз.

Формат ввода

Первая строка содержит два целых числа m и n (1≤m,n≤10^5).
Вторая строка содержит m целых чисел a1,a2,…,am(0≤ai≤10 9)— характеристики овец.
Третья строка содержит n целых чисел b1,b2,…,bn(0≤bi≤10 9) — характеристики псов.

Формат вывода

На первой строке выведите число s — максимальное количество овец, которых можно отправить на прогулку за один раз.

На следующих s строках выведите по три числа: номер овцы i, номер пса j, номер пса k. Должны выполняться неравенства bj<ai<bk.

Sample Input:

4 6
2 3 4 5
1 3 2 2 5 2

Sample Output:

2
1 1 2
2 3 5

from bisect import bisect_left, bisect_right


class AnimalGrouping:
    def __init__(self, sheep, dogs):
        # Сортируем овец и собак вместе с их исходными индексами
        self.sheep = sorted((value, index + 1) for index, value in enumerate(sheep))  # Овцы: (значение, индекс)
        self.dogs = sorted((value, index + 1) for index, value in enumerate(dogs))    # Псы: (значение, индекс)

    def find_max_sheep_with_dogs(self):
        # Результат — список из групп вида (овца, пёс1, пёс2)
        result = []
        dog_values = [value for value, _ in self.dogs]  # Отдельный список лишь для значений псов

        for sheep_value, sheep_index in self.sheep:
            # Находим первый индекс псов, у которых характеристика < овцы
            left_index = bisect_left(dog_values, sheep_value)
            # Находим первый индекс псов, у которых характеристика > овцы
            right_index = bisect_right(dog_values, sheep_value)

            # Проверяем, есть ли в списке псы, подходящие под условия
            if left_index > 0 and right_index < len(dog_values):
                # Получаем пару псов, которые подходят текущей овце
                left_dog_value, left_dog_index = self.dogs[left_index - 1]
                right_dog_value, right_dog_index = self.dogs[right_index]

                # Добавляем пару (номер овцы, номера двух псов) в результат
                result.append((sheep_index, left_dog_index, right_dog_index))

                # Удаляем использованных псов, чтобы их невозможно было использовать повторно
                del self.dogs[right_index]  # Удаление правого пса
                del dog_values[right_index]  # Обновление значений характеристик псов
                del self.dogs[left_index - 1]  # Удаление левого пса
                del dog_values[left_index - 1]  # Обновление значений характеристик псов

        return result


# Чтение входных данных
def main():
    m, n = map(int, input().split())  # Количество овец и псов
    sheep = list(map(int, input().split()))  # Характеристики овец
    dogs = list(map(int, input().split()))  # Характеристики псов

    # Создаём объект AnimalGrouping
    grouping = AnimalGrouping(sheep, dogs)
    result = grouping.find_max_sheep_with_dogs()

    # Выводим количество групп
    print(len(result))  # Количество групп (овца, пёс1, пёс2)
    for group in result:
        print(*group)  # Сами группы


# Запускаем main() при выполнении скрипта
if __name__ == "__main__":
    main()

[BDA]

Вообще говоря, 3-й и 6-й псы имеют одинаковую характеристику и в условии вроде нет никаких дополнительных требований (что нужно брать пса с минимальным индексом), так что должен подходить любой из них. Если чуть-чуть помудрить с индексами (чтобы внутри группы собак с одинаковой характеристикой индексы шли по убыванию), то ответ совпадет:

class AnimalGrouping:
    def __init__(self, sheep, dogs):
        # Сортируем овец и собак вместе с их исходными индексами
        self.sheep = sorted((value, index) for index, value in enumerate(sheep, 1))  # Овцы: (значение, индекс)
        self.dogs = sorted((value, -index) for index, value in enumerate(dogs, 1))   # Псы: (значение, индекс)

    def find_max_sheep_with_dogs(self):
        # Результат — список из групп вида (овца, пёс1, пёс2)
        result = []
        dog_values = [value for value, _ in self.dogs]  # Отдельный список лишь для значений псов

        for sheep_value, sheep_index in self.sheep:
            # Находим первый индекс псов, у которых характеристика < овцы
            left_index = bisect_left(dog_values, sheep_value) - 1
            # Находим первый индекс псов, у которых характеристика > овцы
            right_index = bisect_right(dog_values, sheep_value)

            # Проверяем, есть ли в списке псы, подходящие под условия
            if left_index >= 0 and right_index < len(dog_values):
                # Получаем пару псов, которые подходят текущей овце
                left_dog_value, left_dog_index = self.dogs[left_index]
                right_dog_value, right_dog_index = self.dogs[right_index]

                # Добавляем пару (номер овцы, номера двух псов) в результат
                result.append((sheep_index, -left_dog_index, -right_dog_index))

                # Удаляем использованных псов, чтобы их невозможно было использовать повторно
                del self.dogs[right_index]  # Удаление правого пса
                del dog_values[right_index]  # Обновление значений характеристик псов
                del self.dogs[left_index]  # Удаление левого пса
                del dog_values[left_index]  # Обновление значений характеристик псов

        return result

UPD. "Перевернутые" индексы хороши только для "левой" собаки, но портят "правую". Пока в голову пришла только идея делать второй поиск для "левой" собаки, чтобы брать минимальный индекс.

class AnimalGrouping:
    def __init__(self, sheep, dogs):
        # Сортируем овец и собак вместе с их исходными индексами
        self.sheep = sorted((value, index) for index, value in enumerate(sheep, 1))  # Овцы: (значение, индекс)
        self.dogs = sorted((value, index) for index, value in enumerate(dogs, 1))   # Псы: (значение, индекс)

    def find_max_sheep_with_dogs(self):
        # Результат — список из групп вида (овца, пёс1, пёс2)
        result = []
        dog_values = [value for value, _ in self.dogs]  # Отдельный список лишь для значений псов

        for sheep_value, sheep_index in self.sheep:
            # Находим первый индекс псов, у которых характеристика < овцы
            left_index = bisect_left(dog_values, sheep_value)
            if left_index <= 0:
                continue
            left_index = bisect_left(dog_values, dog_values[left_index - 1], 0, left_index)
            # Находим первый индекс псов, у которых характеристика > овцы
            right_index = bisect_right(dog_values, sheep_value)

            # Проверяем, есть ли в списке псы, подходящие под условия
            if right_index < len(dog_values):
                # Получаем пару псов, которые подходят текущей овце
                left_dog_value, left_dog_index = self.dogs[left_index]
                right_dog_value, right_dog_index = self.dogs[right_index]

                # Добавляем пару (номер овцы, номера двух псов) в результат
                result.append((sheep_index, left_dog_index, right_dog_index))

                # Удаляем использованных псов, чтобы их невозможно было использовать повторно
                del self.dogs[right_index]  # Удаление правого пса
                del dog_values[right_index]  # Обновление значений характеристик псов
                del self.dogs[left_index]  # Удаление левого пса
                del dog_values[left_index]  # Обновление значений характеристик псов

        return result

[Nicodim]

Благодарю за помощь в решении задачи!!!