В состязаниях участвуют N (N - до 100000) спортсменов. Каждому даются три попытки. Входной файл содержит 3 строки с положением участников в каждой попытке (ни в одной из попыток невозможно двум и более человекам разделить одно место).
Считается, что спортсмен A сильнее спортсмена B в случае, если A занял во всех попытках места выше, чем B. А является лучшим среди всех, если нет никого лучше его.
Найти и вывести в выходной файл количество лучших спортсменов.
Реализацию напишу сам, но подскажите алгоритм.
Пока просматривается следующее.
Поскольку раздел мест невозможен, то представляя лучшее и худшее место спортсмена во всех попытках как координаты отрезка, задача сводится к определению количества связных областей в начале координатной прямой.
Т.е. реализация в самом общем виде что-то типа такого:
- считать данные в массив, где каждому спортсмену отводится по 2 позиции: на первой лучшее место, на второй худшее место
- с первой позицией связываем +1, со второй - -1 (можно использовать либо пару массивов, либо один, но с несколько более сложной структурой элементов - в принципе, это сейчас не интересует)
- сортируем массив (второй - по результатам первого)
- осталось посчитать сумму первых +/-1 до получения первого нуля.
Количество +1 дает количество победителей.
Особо смущает факт, что сортировка должна быть стабильной. А это сразу увеличивает время, особенно на больших количествах. Это наталкивает на грустную мысль, что само решение неверное.
Подскажите, пожалуйста, правильный ли подход в принципе. Жаль тратить время на неправильное решение.