基于优先级的合同列表扁平化算法修复与优化诉求

我有一组带时间跨度的Contract列表，部分合同优先级更高。当两份合同时间重叠时，需要对低优先级合同做处理：要么切割成两段、要么从头部/尾部切割，要么直接完全移除。

目前已经实现了相关算法，但输出仍存在错误，推测原因是低优先级合同被切割为两段并添加到结果列表后，原未切割的合同没被移除，导致结果冗余。

Contract类包含DateTime start、DateTime end、double price、int priority属性，有按优先级排序的方法；ContractComparer类用于按起始日期排序。

List<Contract> resultContracts = new List<Contract>()
{
    contractList[0]
};
int n = contractList.Count;
for (var i = 0; i < contractList.Count; i++)
{

    var lastProcessedContract = contractList[i]; // high priority
    var contractsToRemove = new List<Contract>();

    for (var j = i + 1;  j < contractList.Count; j++){

        var lessPriorityContract = contractList[j];

        if (lessPriorityContract.start >= lastProcessedContract.start && lessPriorityContract.end <= lastProcessedContract.end)
        /*
         *  ------------------------>
         *           ------>
         * oder
         *  ------------------------>
         *  -------->
         *  oder
         *  ------------------------->
         *                    ------->
         *
         * oder
         * --------------------------->
         * --------------------------->
         */
        {
            contractsToRemove.Add(lessPriorityContract);
        }
        else if ((lessPriorityContract.start < lastProcessedContract.start 
                 && (lessPriorityContract.end > lastProcessedContract.start && lessPriorityContract.end <= lastProcessedContract.end)) || 
                 ((lastProcessedContract.start < lessPriorityContract.end && lastProcessedContract.start > lessPriorityContract.start)
                     && lastProcessedContract.end > lessPriorityContract.end))
       /* 
          *     ------------------------>
          *  ------>
          * oder
          *     ------------------------------->
          * ----------------------------------->
          


        // oder 
         


          *                   --------------->
          *  ------------------------>
        
        */

        {
            lessPriorityContract.end = lastProcessedContract.start.AddDays(-1);
            resultContracts.Add(lessPriorityContract);
        }
        else if (((lessPriorityContract.start < lastProcessedContract.end && lessPriorityContract.start >= lastProcessedContract.start)
                 && lessPriorityContract.end > lastProcessedContract.end) || (lastProcessedContract.start < lessPriorityContract.start &&
                                                                              (lastProcessedContract.end > lessPriorityContract.start && lastProcessedContract.end < lessPriorityContract.end)))
        /*
         * -------------------->
         *            ------------------------->
         *
         * oder
         * -------------------->
         * ---------------------------------->
         *
          


        //oder
         


          *  ------------>
          *       ------------------->
          * 
         */ 
        {
            lessPriorityContract.start = lastProcessedContract.end.AddDays(1);
            resultContracts.Add(lessPriorityContract);
        }
        else if(lessPriorityContract.start < lastProcessedContract.start
                && lessPriorityContract.end > lastProcessedContract.end)
            /*
             *       ------------>
             * --------------------------->
             * oder
             * --------------------------->
             * --------------------------->
             * 
             */
        {

            var contract = new Contract
            {
                start = lessPriorityContract.start,
                end = lastProcessedContract.start.AddDays(-1),
                priority = lessPriorityContract.priority,
                price = lessPriorityContract.price
            };
            //contractList.Remove(contractList[i]);
            //contractList.Add(contract);
            resultContracts.Add(contract);
            contract = new Contract
            {
                start = lastProcessedContract.end.AddDays(1),
                end = lessPriorityContract.end,
                priority = lessPriorityContract.priority,
                price = lessPriorityContract.price
            };
            resultContracts.Add(contract);
            //contractList.Add(contract);
        }
    }
    foreach (var contractToRemove in contractsToRemove)
    {
        contractList.Remove(contractToRemove);
    }

}

resultContracts.Sort(new ContractComparer());

foreach (var flatElement in resultContracts)
{
    Console.WriteLine(flatElement.ToString());
}

核心问题点修正 #

1. 初始结果列表错误：直接把contractList[0]加入结果，后续循环会重复处理，导致冗余。
2. 原合同未移除：切割低优先级合同后，没有将原合同加入移除列表，原合同会留在结果或原列表中。
3. 循环索引混乱：修改contractList（Remove操作）会改变列表长度，外层for循环的索引会跳过元素。

修复后的代码 #

// 先按优先级降序排序，确保高优先级合同先处理
contractList.Sort((a, b) => b.priority.CompareTo(a.priority));

List<Contract> resultContracts = new List<Contract>();
int i = 0;
while (i < contractList.Count)
{
    var highPriorityContract = contractList[i];
    resultContracts.Add(highPriorityContract);
    var contractsToRemove = new List<Contract>();

    for (int j = i + 1; j < contractList.Count; j++)
    {
        var lowPriorityContract = contractList[j];
        bool isRemoved = false;

        // 情况1：低优先级合同完全被覆盖，直接移除
        if (lowPriorityContract.start >= highPriorityContract.start && lowPriorityContract.end <= highPriorityContract.end)
        {
            contractsToRemove.Add(lowPriorityContract);
            isRemoved = true;
        }
        // 情况2：低优先级合同左半部分重叠，切割右半部分
        else if (lowPriorityContract.end > highPriorityContract.start && lowPriorityContract.end <= highPriorityContract.end && lowPriorityContract.start < highPriorityContract.start)
        {
            var newContract = new Contract
            {
                start = lowPriorityContract.start,
                end = highPriorityContract.start.AddDays(-1),
                priority = lowPriorityContract.priority,
                price = lowPriorityContract.price
            };
            resultContracts.Add(newContract);
            contractsToRemove.Add(lowPriorityContract);
            isRemoved = true;
        }
        // 情况3：低优先级合同右半部分重叠，切割左半部分
        else if (lowPriorityContract.start >= highPriorityContract.start && lowPriorityContract.start < highPriorityContract.end && lowPriorityContract.end > highPriorityContract.end)
        {
            var newContract = new Contract
            {
                start = highPriorityContract.end.AddDays(1),
                end = lowPriorityContract.end,
                priority = lowPriorityContract.priority,
                price = lowPriorityContract.price
            };
            resultContracts.Add(newContract);
            contractsToRemove.Add(lowPriorityContract);
            isRemoved = true;
        }
        // 情况4：低优先级合同完全覆盖高优先级合同，切割为两段
        else if (lowPriorityContract.start < highPriorityContract.start && lowPriorityContract.end > highPriorityContract.end)
        {
            // 左段
            var leftContract = new Contract
            {
                start = lowPriorityContract.start,
                end = highPriorityContract.start.AddDays(-1),
                priority = lowPriorityContract.priority,
                price = lowPriorityContract.price
            };
            // 右段
            var rightContract = new Contract
            {
                start = highPriorityContract.end.AddDays(1),
                end = lowPriorityContract.end,
                priority = lowPriorityContract.priority,
                price = lowPriorityContract.price
            };
            resultContracts.Add(leftContract);
            resultContracts.Add(rightContract);
            contractsToRemove.Add(lowPriorityContract);
            isRemoved = true;
        }

        // 如果原合同被处理（移除/切割），后续不需要再处理它
        if (isRemoved)
        {
            j--; // 因为移除后列表长度减1，调整索引
        }
    }

    // 移除已处理的低优先级合同
    foreach (var contractToRemove in contractsToRemove)
    {
        contractList.Remove(contractToRemove);
    }
    i++;
}

// 按起始日期排序输出
resultContracts.Sort(new ContractComparer());
foreach (var contract in resultContracts)
{
    Console.WriteLine(contract.ToString());
}

思路 #

先按优先级降序排序（优先级相同按起始日期升序），确保高优先级合同先被处理。然后维护一个已处理的合同列表，逐个处理后续低优先级合同：针对每个低优先级合同，先保留其完整时间段，再与已处理的所有高优先级合同对比，切割掉重叠部分，最后将剩余的有效时间段加入结果。

代码实现 #

// 1. 按优先级降序排序，优先级相同则按start升序
contractList.Sort((a, b) => 
{
    int priorityCompare = b.priority.CompareTo(a.priority);
    return priorityCompare != 0 ? priorityCompare : a.start.CompareTo(b.start);
});

List<Contract> result = new List<Contract>();

foreach (var currentContract in contractList)
{
    // 保留当前合同的可用时间段，初始为完整时间段
    List<Tuple<DateTime, DateTime>> availableTimeRanges = new List<Tuple<DateTime, DateTime>>
    {
        Tuple.Create(currentContract.start, currentContract.end)
    };

    // 与已处理的所有高优先级合同对比，切割重叠部分
    foreach (var processedContract in result)
    {
        List<Tuple<DateTime, DateTime>> newAvailableRanges = new List<Tuple<DateTime, DateTime>>();

        foreach (var range in availableTimeRanges)
        {
            DateTime rangeStart = range.Item1;
            DateTime rangeEnd = range.Item2;

            // 无重叠，直接保留
            if (rangeEnd < processedContract.start || rangeStart > processedContract.end)
            {
                newAvailableRanges.Add(range);
                continue;
            }

            // 左半部分无重叠，保留
            if (rangeStart < processedContract.start)
            {
                newAvailableRanges.Add(Tuple.Create(rangeStart, processedContract.start.AddDays(-1)));
            }

            // 右半部分无重叠，保留
            if (rangeEnd > processedContract.end)
            {
                newAvailableRanges.Add(Tuple.Create(processedContract.end.AddDays(1), rangeEnd));
            }
        }

        availableTimeRanges = newAvailableRanges;
        if (!availableTimeRanges.Any())
            break; // 没有可用时间段了，直接退出
    }

    // 将剩余的可用时间段转为Contract对象加入结果
    foreach (var range in availableTimeRanges)
    {
        result.Add(new Contract
        {
            start = range.Item1,
            end = range.Item2,
            priority = currentContract.priority,
            price = currentContract.price
        });
    }
}

// 按起始日期排序输出
result.Sort(new ContractComparer());
foreach (var contract in result)
{
    Console.WriteLine(contract.ToString());
}

优势 #

• 逻辑更清晰：通过维护可用时间段，避免直接修改原合同或列表，减少索引错误
• 扩展性强：新增重叠场景时，只需调整时间段切割逻辑
• 效率更高：排序后只需遍历一次，每个合同的处理逻辑更简洁

内容的提问来源于stack exchange，提问作者Mouad Meziani