Найти самое длинное перекрытие срок


У меня есть список записей, содержащих Id, DateFrom, DateTo. Ради этого вопроса мы можем использовать этот:

List<(int, DateTime, DateTime)> data = new List<(int, DateTime, DateTime)>
        {
            (1, new DateTime(2012, 5, 16), new DateTime(2018, 1, 25)),
            (2, new DateTime(2009, 1, 1), new DateTime(2011, 4, 27)),
            (3, new DateTime(2014, 1, 1), new DateTime(2016, 4, 27)),
            (4, new DateTime(2015, 1, 1), new DateTime(2015, 1, 3)),
        };

В моем реальном случае этот список может быть намного больше, ибо сейчас я предполагаю, что существует только одна запись для определенного Id.

Задача найти две записи, имеет самое длинное время перекрытия и вернуть ID и количество перекрывающихся дней.

Который в данном примере означает, что они должны быть записи 1 и 3, потому что 2 не перекрываются ни с кем, и 4 накладывается на более короткое время.

Моя реализация заключается в следующем:

    public (int, int, int) GetLongestElapsedPeriod(List<(int, DateTime, DateTime)> periods)
    {
        int firstId = -1;
        int secondId = -1;
        int periodInDays = 0;

        foreach (var period in periods)
        {
            var Id = period.Item1;
            var dateFrom = period.Item2;
            var dateTo = period.Item3;

            for (int i = 0; i < periods.Count; i++)
            {
                if (Id != periods[i].Item1)
                {
                    var tempId = periods[i].Item1;
                    var tempDateFrom = periods[i].Item2;
                    var tempDateTo = periods[i].Item3;

                    if (tempDateFrom < dateTo && tempDateTo > dateFrom)
                    {
                        DateTime commonStartingDate = tempDateFrom > dateFrom ? tempDateFrom : dateFrom;
                        DateTime commonEndDate = tempDateTo > dateTo ? dateTo : tempDateTo;

                        var elapsedPeriod = commonEndDate - commonStartingDate;

                        if ((int)elapsedPeriod.TotalDays > periodInDays)
                        {
                            periodInDays = (int)elapsedPeriod.TotalDays;
                            firstId = Id;
                            secondId = tempId;
                        }
                    }
                }
            }
        }
        return (firstId, secondId, periodInDays);
    }

Но я думаю, что этот способ не очень эффективен, и я ищу идеи, чтобы оптимизировать эту логику. Кроме того, я подозреваю, что это вариации на общие алгоритмические проблемы.



192
1
задан 25 января 2018 в 11:01 Источник Поделиться
Комментарии
1 ответ

Я не C# программист.

Во-первых, вы используете for each и вложенные for петли, но оба эти переборем же List. Для последовательности (а для следующего комментария смысл), я предлагаю вам использовать for петли.

for (int i = 0; i < periods.Count; i++)

Вы могли бы начать i не от 0. но из своего current location + 1 во внешнем цикле. Логика этого является то, что вы уже сравнили пары периодов до этого - нет необходимости в двойной ручкой. Поэтому, используя похожие for петель будет легче - вы будете подсчитывать, где вы находитесь в List во внешнем цикле.

Сделав это небольшое изменение означает, что if (Id != periods[i].Item1 больше не нужен - снижает один уровень вложенности в коде.

Как значимое имя, я бы назвал commonStartingDate и commonEndDate overlapStart и overlapEnd соответственно - это более подробно описать, что вы подразумеваете.
overlapStart = max(period1.Start, period2.Start)
overlapEnd = min(period1.End,period2.End)

Ошибка проверки: проверить, что Item2 всегда меньше Item3 (и исправить если не так), в противном случае ваша логика будет нарушена.

Можно упростить var elapsedPeriod = commonEndDate - commonStartingDate и следующий код, используя:

int elapsedPeriod = (int)(commonEndDate - commonStartingDate).TotalDays 

Не может выглядеть проще, но в следующий блок:

                if (elapsedPeriod > periodInDays)
{
periodInDays = elapsedPeriod;
firstId = Id;
secondId = tempId;

Вы не используете elapsedPeriod ни для чего другого.

Основная логика это хорошо - я помню, что решить эту проблему 25 лет назад при разработке базы данных бронирования отелей.

3
ответ дан 26 января 2018 в 04:01 Источник Поделиться