The folloging image tries to represent a list of time slots. with the last line representing the merged result. Each slot is composed with both start/end (date and time) and a type (green/yellow). The final result needs to return the merged slots with some rules, where if there is a green overlapped with yellow, the green prevails.

My approach at the moment is to start with an ordered list by time. but at this moment my code is getting messy and somehow using recursive logic.... and I am not sure if this is the easiest approach.

It would be easy if the "time slots" were somehow unique in size, but that is not the case since I am dealing with minutes/seconds... and the "overlapping" can coincise with such small units.

I am not asking for a solution code, but some help, pointing me some known algorithms that are used for this type of problems. Some page urls that I can read or such. Thank you.

CodePudding user response：

If you work with sorted lists, the solution is pretty easy.

Split every interval in a start and an end time, with a 1 and -1 label each. If you need to implement extra logic based on color, integrate that information in the label.

Now sort all times increasingly (with a full sort or with a merge if the lists are initially sorted). By processing in increasing time, you will maintain the number of tasks in progress. Their union corresponds to a nonzero number. You can implement any rule you want based on the "colored" numbers.

CodePudding user response：

I think I found a solution that at first sight looks easy. I still need to test it with some other samples... but I believe that if there is still any bug, the solution will not increase its complexity.

Anyway, feel free to help me improve it. Thanks

/***************************************************************************/
var processDateTime = filter.From;
var continueLoop = true;                    
while (continueLoop)
{
    var target = mergedMachineSlotsOfTimeRaw.Where(x => x.From >= processDateTime)
                                            .OrderBy(x => x.From).FirstOrDefault();
    if (target == null)
    {
        continueLoop = false;
    }
    else
    {
        mergedMachineSlotsOfTimeRaw = GetMergedSlot(target, mergedMachineSlotsOfTimeRaw);
        processDateTime = target.To.Value;
    }
}                                                                
/***************************************************************************/

Other function

private List<DTOTempMachineSlot> GetMergedSlot(DTOTempMachineSlot original,
                                       List<DTOTempMachineSlot> originalList)
{
    var overlappedEntries = originalList.Where(x => x.Id != original.Id
                                                    && x.From >= original.From
                                                    && x.From < original.To);
    if (overlappedEntries.Count() == 0)
    {
        return originalList;
    }
    var newFinalList = new List<DTOTempMachineSlot>();
    var longestEntry = overlappedEntries.OrderByDescending(x => x.To).FirstOrDefault();

    var deleteLongestEntry = false;
    if (original.State == longestEntry.State)
    {
        if(original.To < longestEntry.To) {
                  original.To = longestEntry.To;
        }
        deleteLongestEntry = true;
    }
    else if (original.State == "S" && longestEntry.State == "E")
    {
        original.To = original.To;
        longestEntry.From = original.To.Value;
    }
    else if (original.State == "E" && longestEntry.State == "S")
    {
        original.To = longestEntry.To;
    }

    newFinalList.Add(original);
    if (deleteLongestEntry == false)
    {
        newFinalList.Add(longestEntry);
    }
    newFinalList.AddRange(originalList.Where(x => x.Id != original.Id 
                    && overlappedEntries.Any(y=>y.Id == x.Id) == false));

    return newFinalList;
}