CODEWITHSUNDEEP
c#
Tony_Henrich
Tony_Henrich

Reputation: 44085

How to create a list of time ranges based on intersections from two lists of time ranges?

I have a problem needing a c# solution, the issue became too complex for a simple solution.

I have two lists of time ranges plus a value for each range: ListA; ListB. There's no relationship between them.

I would like to create a third list (ListC) based on ListB where for every start and end pair in ListB, if the range doesn't exist as a whole in any time range in ListA, create two or more entries in ListC so that the new entries are covered by entries in ListA. (Sorry it's hard to explain without being too verbose)

A simple example which contains one kind of overlap. There could be all kinds of overlaps between the two lists.

List<Tuple<int, DateTime, DateTime>> listA = new List<Tuple<int, DateTime, DateTime>>();          
listA.Add(new Tuple<int, DateTime, DateTime>(22,DateTime.Parse("09/01/2013 11:00"),DateTime.Parse("09/01/2013 12:00")));
listA.Add(new Tuple<int, DateTime, DateTime>(66, DateTime.Parse("09/01/2013 12:01"), DateTime.Parse("09/01/2013 14:00")));


List<Tuple<int, DateTime, DateTime>> listB = new List<Tuple<int, DateTime, DateTime>>();
listB.Add(new Tuple<int, DateTime, DateTime>(33, DateTime.Parse("09/01/2013 11:30"), DateTime.Parse("09/01/2013 13:30")));

//Desired List
List<Tuple<int, DateTime, DateTime>> listC = new List<Tuple<int, DateTime, DateTime>>();
//listC should contain 2 tuples: first tuple contains the segment from ListB which falls in the first ListA tuple: Tuple(33, "09/01/2013 11:30","09/01/2013 12:00")
//second tuple contains the segment which falls in second ListA tuple: Tuple(33, "09/01/2013 12:01","09/01/2013 13:30")

Upvotes: 1

Views: 436

Answers (3)

user687474
user687474

Reputation:

You can use the Time Period Library for .NET to calculate the intersections:

// ----------------------------------------------------------------------
public void PeriodIntersection()
{
  // time periods
  ITimePeriodCollection periods = new TimePeriodCollection();
  periods.Add( new TimeRange( new DateTime( 2013, 9, 1, 11, 0, 0 ), new DateTime( 2013, 9, 1, 12, 0, 0 ) ) );
  periods.Add( new TimeRange( new DateTime( 2013, 9, 1, 12, 1, 0 ), new DateTime( 2013, 9, 1, 14, 0, 0 ) ) );

  // search range
  TimeRange searchRange = new TimeRange( new DateTime( 2013, 9, 1, 11, 30, 0 ), new DateTime( 2013, 9, 1, 13, 30, 0 ) );

  // intersections
  foreach ( TimeRange period in periods )
  {
    if ( period.IntersectsWith( searchRange ) )
    {
      Console.WriteLine( "Intersection: " + period.GetIntersection( searchRange ) );
    }
  }
  // > Intersection: 01.09.2013 11.30:00 - 12:00:00 | 0.00:30
  // > Intersection: 01.09.2013 12.01:00 - 13:30:00 | 0.01:29
} // PeriodIntersection

Upvotes: 0

Code Uniquely
Code Uniquely

Reputation: 6373

It would help you significantly if you used a class along these lines to hold your data.

public class Range 
{
    public int Id {get; set:}
    public DateTime Start {get; set:}
    public DateTime End {get; set:}
}

It would make it easier for you to compare each of the values in List B with each of the the Start and End values in List A to see if there is any overlap (of which there are only 4 possible types)

Type 1: B.Start < A.Start && B.End > A.End      (where B totally contains A)
Type 2: B.Start >= A.Start && B.End <= A.End    (where A totally contains B)
Type 3: B.Start >= A.Start && B.Start <= A.End  (where B overlaps to the right)
Type 4: B.End >= A.Start && B.End <= A.End      (where B overlaps to the left)

Pseudo code is something like

Loop through all entries in List B
{
    Loop through all entries in A looking for overlaps
    {
        If there is an overlap
        {
            Create a new range from the
            appropriate Start and End values 
            from A or B as required.

            Use the ID from B 

            Add new Range(s) as required
        }
    }
}

Upvotes: 0

Alexey
Alexey

Reputation: 919

Here is my try. The solution is quite straightforward, maybe I misunderstood the task. You might want to cosider if you need using <=, >= instead of <,> in the lines specified in the comments:

        List<Tuple<int, DateTime, DateTime>> listA = new List<Tuple<int, DateTime, DateTime>>();
        listA.Add(new Tuple<int, DateTime, DateTime>(22, DateTime.Parse("09/01/2013 11:00"), DateTime.Parse("09/01/2013 12:00")));
        listA.Add(new Tuple<int, DateTime, DateTime>(66, DateTime.Parse("09/01/2013 12:01"), DateTime.Parse("09/01/2013 14:00")));


        List<Tuple<int, DateTime, DateTime>> listB = new List<Tuple<int, DateTime, DateTime>>();
        listB.Add(new Tuple<int, DateTime, DateTime>(33, DateTime.Parse("09/01/2013 11:30"), DateTime.Parse("09/01/2013 13:30")));

        List<Tuple<int, DateTime, DateTime>> listC = new List<Tuple<int, DateTime, DateTime>>();

        foreach (var rangeB in listB)
        {
            //a range in A overlaps with a range B 
            //if any end of the range in A is inside the range in B
            //consider using <= and/or >= in these two lines if needed
            var overlapping = listA.Where(rangeA => rangeB.Item2 < rangeA.Item2 && rangeA.Item2 < rangeB.Item3 ||
                rangeB.Item2 < rangeA.Item3 && rangeA.Item3 < rangeB.Item3).ToList();

            overlapping = overlapping.Select(rangeA => 
                new Tuple<int, DateTime, DateTime> (rangeB.Item1, 
                    //If a date of A is outside of B
                    //this will make it equal to the corresponding date of B
                    (rangeA.Item2 < rangeB.Item2) ? rangeB.Item2 : rangeA.Item2,
                    (rangeB.Item3 < rangeA.Item3) ? rangeB.Item3 : rangeA.Item3)).ToList();

            listC.AddRange(overlapping);
        }

Upvotes: 1

Related Questions