Acvik2402, Надо перед складыванием отрезков в массив и сортирвкой сдвигать на +1 конец или на -1 начало.
И потом, у вас там слишком запутанная логика, я в ней даже разобраться не могу. Просто перепишите, как я вам подсказал - сначала получите все отрезки, потом уже ищите там максимум.
Acvik2402, Ну раз разные вакансии =разные интервалы, то объеденять их не нужно. Смотрите мое решение и уберите ```if(... .cnt != cnt)```. Всегда добавляйте новый отрезок.
Похоже, единственная ваша ошибка была - в не сдвигании концов на +-1, чтобы они были точками на прямой.
Acvik2402, Возможно, ошибка в примере. Спросите у авторов, почему так. Ведь 4 подряд идущих секунд открыто по одной вакансии.
Но если за разные считаются интервалы с разным множеством открытых вакансий, то мое решение можно просто исправить - надо всегда добавлять новый отрезок в массив result, если у него ненулевая длина и удалить увеличение длины последнего отрезка.
Acvik2402, тест "3 1 1 1 2 2 3" - тут первый отрезок занимает всю первую секунду, а второй отрезок занимает первую и вторую секунду. Потому что сказано в условии, что отрезки включают концы.
Когда вы сортируете события на прямой - эти события должны быть точками. Дак вот точка конца первого отрезка в координате 1, а начало в точке 0. У второго отрезка начало в координате 0, а конец в координате 2. У третьего начало в 1, конец в 3.
Можно или сдвигать концы на +1 или начала на -1 - не важно. Если не сдвигать и просто отсортировать, то у вас получается, что отрезки длины 1, где они пересекаются вы не учитываете.
Bavashi, как раз mn и есть самая точная оценка, ибо m может быть порядка n^2. Т.е. Форд-Беллман будет n^2 на сильно разряженном графе и n^3 на плотном.
Acvik2402, Ваши 2 мапа проверяют, что строку 1 можно преобразовать в строку 2 и обратно. Но есть примеры, когда можно сделать преобразование только в одну сторону. Еще раз: "аб" можно превратить в "аа" ('а'=>'а', б'=>'а'). Обратно - нет, ибо одну 'а' надо оставить, а другую заменить.
Вам надо оставить ваш map1 c его проверками. Но для исключения случая, когда не хватает промежуточных символов для выполнения замен, надо подсчитать количество различных значений в этом мапе (не ключей, а имеено значений из второй строки). Это можно сделать с помощью сета, куда надо сложить вторую строку и проверить его размер.
Acvik2402, Потому что обратный мап не нужен. Вы можете преобразовать "ааб" в "ввв", но не обратно. Вместо обратного мапа заведите сет. Если там 33 элемента, то ответ 0.
Vadim Shorin, Код в вопросе - правильный и выведет с 50 по 5000 элементы.
В вашем рабочем коде какая-то другая ошибка. Может вы где-то память портите, может опечатка банальная. Придется приводить рабочий код. Оставьте только ввод и вывод, можете переименовать переменные, если имена секретные.
