Combine Time Ranges

问题:

I am currently working on a C# program where I have the need to combine a bunch of time ranges. For each range I have the start and end time. I found an example where this was being done in Ruby but not for C#. I am basically looking for the time range union. I feel like there might be a way to do this using linq but I cant come up with it. Any ideas?

So for example

Start Time: 1:30 End Time: 2:00

Start Time: 1:45 End Time: 2:30

Start Time: 3:00 End Time: 5:00

Start Time: 4:00 End Time: 4:30

Start Time: 4:45 End Time: 5:30

This set of times would come back as

Start Time: 1:30 End Time: 2:30

Start Time: 3:00 End Time: 5:30

回答1:

You could have a look at this project which supports TimeRanges and intersection methods:

http://www.codeproject.com/Articles/168662/Time-Period-Library-for-NET

回答2:

This looked fun so I started coding something.

public class TimeRanges
{
    private List<TimeRange> _mergedTimeRanges = new List<TimeRange>();

    public void Add(TimeRange timeRange)
    {
        if(!_mergedTimeRanges.Any(x=>x.IsOverLap(timeRange)))
        {
            _mergedTimeRanges.Add(timeRange);
            return;
        }
        while (_mergedTimeRanges.Any(x => x.IsOverLap(timeRange) && x!=timeRange))
        {
            TimeRange toMergeRange = _mergedTimeRanges.First(x => x.IsOverLap(timeRange));
            toMergeRange.Merge(timeRange);
            timeRange = toMergeRange;
        }
    }

    public IEnumerable<TimeRange> GetMergedRanges()
    {
        return _mergedTimeRanges;
    }
}

public class TimeRange
{
    public DateTime Start { get; private set; }
    public DateTime End { get; private set; }
    public TimeRange(DateTime start, DateTime end)
    {
        if (start >= end)
            throw new ArgumentException("Invalid time range, end must be later than start");
        Start = start;
        End = end;
    }

    public void Merge(TimeRange timeRange)
    {
        if (!IsOverLap(timeRange))
            throw new ArgumentException("Cannot merge timeranges that don't overlap", "timeRange");
        if (End < timeRange.End)
            End = timeRange.End;
        if (timeRange.Start < Start)
            Start = timeRange.Start;
    }

    public bool IsOverLap(TimeRange timeRange)
    {
        if (timeRange.End < Start)
            return false;
        if (timeRange.Start > End)
            return false;
        return true;
    }

    public bool Equals(TimeRange other)
    {
        if (ReferenceEquals(null, other)) return false;
        if (ReferenceEquals(this, other)) return true;
        return other.Start.Equals(Start) && other.End.Equals(End);
    }

    public override bool Equals(object obj)
    {
        if (ReferenceEquals(null, obj)) return false;
        if (ReferenceEquals(this, obj)) return true;
        if (obj.GetType() != typeof (TimeRange)) return false;
        return Equals((TimeRange) obj);
    }

    public override int GetHashCode()
    {
        unchecked
        {
            return (Start.GetHashCode()*397) ^ End.GetHashCode();
        }
    }
}

I have a couple of tests for it if anyone would be interested

回答3:

Johan Larsson's answer helped me a lot. I used it, and hit an infinite while loop in the following case so I thought I'd contribute.

Start Time: 1:30 End Time: 2:00

Start Time: 2:45 End Time: 4:00

Start Time: 1:45 End Time: 3:00 (overlaps the first two ranges)

So here is a condensed version of what I came up with:

private static IEnumerable<TimeRange> MergeTimeRanges(IEnumerable<TimeRange> ranges)
{
    var mergedRanges = new List<TimeRange>();

    foreach (var range in ranges)
    {
        var overlapping = mergedRanges.Where(r => !(range.End < r.Start) && !(range.Start> r.End)).ToArray();
        if (overlapping.Length == 0)
        {
            mergedRanges.Add(range);
        }
        else
        {
            // add a new range made up of the overlapping ranges plus the new range, then delete the ovelapping ranges
            mergedRanges.Add(new TimeRange { Start = Math.Min(range.Start, overlapping.Min(r => r.Start)), End = Math.Max(range.End, overlapping.Max(r => r.End)) });
            foreach (var r in overlapping)
                mergedRanges.Remove(r);
        }
    }

    return mergedRanges;
}

Note: On second thought, the infinite loop problem might have been avoided by ordering the initial ranges (?). Not sure.