C
C#•2w ago
Thalnos

✅ Help with an Algorithm on time intervals

Sooo I want to create a discord bot that helps our alliance schedule events by evaluating how many members are available at what time intervals My users will input a start and end time when they are available. I got an idea in mind how to solve it and just wanna make sure my algorithm is right: 
var result = new Dictionary<(TimeOnly, TimeOnly), int>();
var intervals = Availables.Values.OrderBy(interval => interval.Item1).ToList(); //sort by start time
var interval = intervals.First();
var availableMembers = 1;
for (var i = 1; i < Availables.Count; i++)
{
    var currentInterval = intervals[i];
    var currentStart = currentInterval.Item1;
    var currentEnd = currentInterval.Item2;
    var previousInterval = intervals[i - 1];
    var previousEnd = previousInterval.Item2;
    if (currentStart > previousEnd) //no overlap
    {
        result.Add(interval, availableMembers);
        availableMembers = 1;
        continue;
    }
    availableMembers++;
    var minEnd = currentEnd < previousEnd ? currentEnd : previousEnd;
    interval = (currentStart, minEnd);
}
return result;
var result = new Dictionary<(TimeOnly, TimeOnly), int>();
var intervals = Availables.Values.OrderBy(interval => interval.Item1).ToList(); //sort by start time
var interval = intervals.First();
var availableMembers = 1;
for (var i = 1; i < Availables.Count; i++)
{
    var currentInterval = intervals[i];
    var currentStart = currentInterval.Item1;
    var currentEnd = currentInterval.Item2;
    var previousInterval = intervals[i - 1];
    var previousEnd = previousInterval.Item2;
    if (currentStart > previousEnd) //no overlap
    {
        result.Add(interval, availableMembers);
        availableMembers = 1;
        continue;
    }
    availableMembers++;
    var minEnd = currentEnd < previousEnd ? currentEnd : previousEnd;
    interval = (currentStart, minEnd);
}
return result;
I sort the input by start time I remember an interval which is where I store a merge when there is overlap between two intervals When there is no overlap I add the interval to my result and reset the amount of available members back to 1 When there is I increment the available members, and merge then interval using the current start (which is the max start up to now as I've sorted) and the min end. Does this look right to you? One potential problem I see with my algorithm is when say there is 12:30 - 17:30 and then 13:00 - 14:00 after, we take the minimum of 14:00 to merge and keep traversing with that but we disregard that previous member is available from 14:00-17:30
2 Replies
Cracker
Cracker•2w ago
Maybe consider concurrence
Thalnos
ThalnosOP•2w ago
can you ellaborate pls? I was able to solve it. I just seperated the problem into two steps, first building all the intervals, and then checking if there is an entry within an interval. It's maybe not the best optimal solution but it does the job 😊 
Dictionary<(TimeOnly, TimeOnly), int> GetAvailabilities()
{
    var result = new Dictionary<(TimeOnly, TimeOnly), int>();
    var distinctOrderedTimes = availables.Values
        .SelectMany(interval => new[] { interval.Item1, interval.Item2 })
        .Distinct()
        .Order()
        .ToList();
    var intervals = availables.Values.ToList();
    for (int i = 0; i < distinctOrderedTimes.Count - 1; i++)
    {
        var start = distinctOrderedTimes[i];
        var end = distinctOrderedTimes[i + 1];
        var count = 0;
        foreach (var (intervalStart, intervalEnd) in intervals)
        {
            if (intervalStart <= start && intervalEnd >= end)
                count++;
        }
        if (count > 0)
            result[(start, end)] = count;
    }
    return result;
}
Dictionary<(TimeOnly, TimeOnly), int> GetAvailabilities()
{
    var result = new Dictionary<(TimeOnly, TimeOnly), int>();
    var distinctOrderedTimes = availables.Values
        .SelectMany(interval => new[] { interval.Item1, interval.Item2 })
        .Distinct()
        .Order()
        .ToList();
    var intervals = availables.Values.ToList();
    for (int i = 0; i < distinctOrderedTimes.Count - 1; i++)
    {
        var start = distinctOrderedTimes[i];
        var end = distinctOrderedTimes[i + 1];
        var count = 0;
        foreach (var (intervalStart, intervalEnd) in intervals)
        {
            if (intervalStart <= start && intervalEnd >= end)
                count++;
        }
        if (count > 0)
            result[(start, end)] = count;
    }
    return result;
}

Did you find this page helpful?