asp.netlinqsortingdate

Sorting a List based on Start and End dates with no Overlapping dates


I have a concept which I have trouble into converting it into code.

The basic idea is as shown below image

Display data with non-overlapping dates

The picture might not say much. To describe the issue, I have a List of data with structure as below.

public class DateVM {
    public int Group { get; set; }
    public string Text { get; set; }
    public string BackColor { get; set; }
    public DateTime StartDate { get; set; }
    public DateTime EndDate { get; set; }
    public bool IsSorted {get;set;}
}

By default, the (int) Group value is 0. What I need to do is sort the records in the list and update the group value as shown in the picture where the dates do not overlap.

There could be gaps between the dates or they can continue one after the other, I am trying to put the records into groups where they do not overlap.

Sample Data
{Group:0, Text:Record1, BackColor:Red, StartDate:10/02/2025, EndDate:16/02/2025}
{Group:0, Text:Record2, BackColor:Green, StartDate:17/02/2025, EndDate:20/02/2025}
{Group:0, Text:Record3, BackColor:Blue, StartDate:17/02/2025, EndDate:20/02/2025}
{Group:0, Text:Record4, BackColor:Red, StartDate:21/02/2025, EndDate:23/02/2025}
{Group:0, Text:Record5, BackColor:Blue, StartDate:21/02/2025, EndDate:23/02/2025}
{Group:0, Text:Record6, BackColor:Green, StartDate:24/02/2025, EndDate:03/03/2025}
{Group:0, Text:Record7, BackColor:Blue, StartDate:24/02/2025, EndDate:02/03/2025}
{Group:0, Text:Record8, BackColor:Red, StartDate:04/03/2025, EndDate:09/03/2025}
{Group:0, Text:Record9, BackColor:Green, StartDate:04/03/2025, EndDate:09/03/2025}
{Group:0, Text:Record10, BackColor:Red, StartDate:19/02/2025, EndDate:20/02/2025}

Needed Output
{Group:1, Text:Record1, BackColor:Red, StartDate:10/02/2025, EndDate:16/02/2025}
{Group:1, Text:Record2, BackColor:Green, StartDate:17/02/2025, EndDate:20/02/2025}
{Group:2, Text:Record3, BackColor:Blue, StartDate:17/02/2025, EndDate:20/02/2025}
{Group:1, Text:Record4, BackColor:Red, StartDate:21/02/2025, EndDate:23/02/2025}
{Group:2, Text:Record5, BackColor:Blue, StartDate:21/02/2025, EndDate:23/02/2025}
{Group:1, Text:Record6, BackColor:Green, StartDate:24/02/2025, EndDate:03/03/2025}
{Group:2, Text:Record7, BackColor:Blue, StartDate:24/02/2025, EndDate:02/03/2025}
{Group:1, Text:Record8, BackColor:Red, StartDate:04/03/2025, EndDate:09/03/2025}
{Group:2, Text:Record9, BackColor:Green, StartDate:04/03/2025, EndDate:09/03/2025}
{Group:3, Text:Record10, BackColor:Red, StartDate:19/02/2025, EndDate:20/02/2025}

The above intended process is to optimize the time consumed in term of data display on UI.

I am currently displaying the data, one after the other where I compare each records Start date to see if the range already exists, if so, I move the data to next row for display, and so on until all records are handled. This process takes long time if the RecordSet is big.

If I can sort the data beforehand into groups, I would not have to do the comparison one by one and can just push the data to display in its respective rows.

Current process is Sorting by start date

dateVM.Sort(DatebarVMComparer.CompareByStartDate);

public static int CompareByStartDate(DateVM x, DateVM y)
{
    if (x == null)
    {
        if (y == null)
        {
            // If x is null and y is null, they're equal. 
            return 0;
        }
        else
        {
            // If x is null and y is not null, y is greater. 
            return -1;
        }
    }
    else
    {
        // If x is not null and y is null, x is greater.
        if (y == null)
        {
            return 1;
        }
        else
        {
            // ...and y is not null, compare the StartDate
            int retval = DateTime.Parse(x.StartDate).CompareTo(DateTime.Parse(y.StartDate));
            return retval;
        }

    }
}

This works for small record Sets but is very inefficient. and will use too many resources.


I also found few examples in react using moment-range.js where you can define a range and check if a date is with in the range.

Are there any libraries I can use in my scenario.


I am looking for ideas/inputs to better this process. to use as less resources as possible.


Update:

I have attained the desired result as below:

public static IList<SomeObjectNonOverlapping> SortToNonOverlappingDates(List<DateVM> bars)
{
    IList<SomeObjectNonOverlapping> response = new List<SomeObjectNonOverlapping>();
    response = bars.Select((t, i) => new SomeObjectNonOverlapping
    {
        Text = t.Text,
        BackColor = t.BackColor,
        StartDate = DateTime.Parse(t.StartDate),
        EndDate = DateTime.Parse(t.EndDate),
        IsSorted = false
    }).ToList();

    var group = 1;
    response.First().Group = group;
    response.First().IsSorted = true;

    for (var i = 1; i < response.Count; i++)
    {
        group = response.Max(x => x.Group);

        for (var g = 1; g <= group; g++)
        {
            if (!response.Where(x => x.IsSorted && x.Group == g).Except(response[i]).Any(range => (response[i].StartDate >= range.StartDate && response[i].StartDate <= range.EndDate)))
            {
                response[i].Group = g;
                response[i].IsSorted = true;
                break;
            }
            else
            {
                group++;  
            }
        }
    }
    return response;
}

Any advice on making things even faster and better. Please leave a response

Thank you.


Solution

  • Sort intervals by StartDate. For each interval: Place it in the first group where it doesn't overlap. If no such group exists, create a new one. Time: O(n log n) for sorting + O(n × g) for assignment (In practice, g << n, so it scales well.) Space: O(g) where g is the number of groups

    public static IList<DateVM> AssignGroups(List<DateVM> records)
    {
        // Step 1: Sort by StartDate
        var sorted = records.OrderBy(r => r.StartDate).ToList();
    
        // Step 2: Keep track of the latest EndDate for each group
        var groupEndDates = new List<DateTime>();
        int groupCount = 0;
    
        foreach (var record in sorted)
        {
            bool placed = false;
    
            for (int i = 0; i < groupEndDates.Count; i++)
            {
                if (record.StartDate > groupEndDates[i]) // no overlap
                {
                    record.Group = i + 1; // 1-based group index
                    groupEndDates[i] = record.EndDate;
                    placed = true;
                    break;
                }
            }
    
            if (!placed)
            {
                // Create a new group
                groupEndDates.Add(record.EndDate);
                groupCount++;
                record.Group = groupCount;
            }
    
            record.IsSorted = true;
        }
    
        return sorted;
    }
    
    

    PS: I took help of AI to format code for my rough Idea and it also suggested the name Greedy Scheduling Algorithm