none
Newbie question to use LINQ in C# RRS feed

  • Question

  • Hello:

    I have a list of courses (fixtures), which include the begin and end time, and the credit.

            public class cours
            {
                public int coursID { get; set; }
                public DateTime beginTime { get; set; }
                public DateTime endTime { get; set; }
                public int credit { get; set; }
            }
    
    
            static void Main(string[] args)
            {
                List<cours> fixtures = new List<cours>();
                fixtures.Add(new cours
                {
                    coursID = 1,
                    beginTime = DateTime.Today.AddHours(33.0),
                    endTime = DateTime.Today.AddHours(35.0),
                    credit = 5
                });
    
                fixtures.Add(new cours
                {
                    coursID = 2,
                    beginTime = DateTime.Today.AddHours(34.0),
                    endTime = DateTime.Today.AddHours(36.0),
                    credit = 10
                });
    
                fixtures.Add(new cours
                {
                    coursID = 3,
                    beginTime = DateTime.Today.AddHours(37.0),
                    endTime = DateTime.Today.AddHours(39.0),
                    credit = 5
                });
    
                fixtures.Add(new cours
                {
                    coursID = 4,
                    beginTime = DateTime.Today.AddHours(40.0),
                    endTime = DateTime.Today.AddHours(42.0),
                    credit = 10
                });
            }
    

    From the list, I want to use LINQ or whatever suitable statements to find out another list, in which, if there is no overlap in the begin, end time, then all the items in the list are returned.

    If there is an overlap in the begin, end time for items in the list, the pick up only the items with higher credit value.

    In the above example, I want to have another list, which includes the items for coursID = 2, coursID = 3, and coursID = 4.  Only discard coursID = 1.

    The reason is: since coursID = 1, its begin time is in 33 hours from now, before its end, which is in 35 hours from now; another item coursID = 2, since its begin time is in 34 hours from now, but coursID = 2 has higher credit of 10, so use coursID = 2 to replace coursID = 1.

    But for coursID = 3, and coursID = 4, the both items stay, as even coursID = 4 has higher credit than that of coursID = 3; but since their begin time and end time don’t overlap, there is one hour before the coursID = 4 will begin after coursID = 3 ends, so they both can stay.

    I can’t figure it out, please advise.

    Thanks,


    Thursday, May 10, 2018 8:57 PM

Answers

  • If you want some LINQ, check this fragment:

    List<cours> result = new List<cours>();
    
    Func<cours, cours, bool> is_overlap =
        ( c1, c2 ) =>
            ( c1.beginTime >= c2.beginTime && c1.beginTime <= c2.endTime ) ||
            ( c1.endTime >= c2.beginTime && c1.endTime <= c2.endTime ) ||
            ( c2.beginTime >= c1.beginTime && c2.beginTime <= c1.endTime ) ||
            ( c2.endTime >= c1.beginTime && c2.endTime <= c1.endTime );
    
    var e = fixtures.OrderByDescending( f => f.credit ).AsEnumerable();
    
    while( e.Any() )
    {
        var c = e.First();
        result.Add( c );
        e = e.Skip( 1 ).Where( f => ! is_overlap( c, f ) ).ToList();
    }

    • Marked as answer by zydjohn Friday, May 11, 2018 1:56 PM
    Friday, May 11, 2018 5:27 AM

All replies

  • I'm not sure LINQ will do it.  You need nested loops here.  And remember, if you delete something from a list while you are looping through the list, it makes your loop suspect.  I think you need a function to make one pass through the list.  If it finds a conflict, it deletes the lesser element, then returns.  The main code can then call that function repeatedly until no other elements are removed.  I believe this does what you want:

    using System;
    using System.IO;
    using System.Text;
    using System.Collections.Generic;
    
    public class cours
    {
        public int coursID { get; set; }
        public DateTime beginTime { get; set; }
        public DateTime endTime { get; set; }
        public int credit { get; set; }
        public void Print()
        {
            Console.WriteLine( "Course {0}, time {1} - {2}, {3} credits",
                coursID, beginTime, endTime, credit 
            );
        }
    }
    
    public class Program
    {
        static bool onepass( List<cours> fixtures )
        {
            foreach( cours a in fixtures )
            {
                foreach( cours b in fixtures )
                {
                    if( a.coursID >= b.coursID )
                        continue;
    // Check for overlap. if(
    (a.beginTime <= b.beginTime && a.endTime >= b.beginTime)
    ||
    (a.beginTime >= b.beginTime && a.beginTime <= b.endTime)
    ) { if( a.credit > b.credit ) fixtures.Remove( b ); else fixtures.Remove( a ); return false; } } } return true; } static void Main(string[] args) { List<cours> fixtures = new List<cours>(); fixtures.Add(new cours { coursID = 1, beginTime = DateTime.Today.AddHours(33.0), endTime = DateTime.Today.AddHours(35.0), credit = 5 }); fixtures.Add(new cours { coursID = 2, beginTime = DateTime.Today.AddHours(34.0), endTime = DateTime.Today.AddHours(36.0), credit = 10 }); fixtures.Add(new cours { coursID = 3, beginTime = DateTime.Today.AddHours(37.0), endTime = DateTime.Today.AddHours(39.0), credit = 5 }); fixtures.Add(new cours { coursID = 4, beginTime = DateTime.Today.AddHours(40.0), endTime = DateTime.Today.AddHours(42.0), credit = 10 }); Console.WriteLine( "Start" ); foreach( cours a in fixtures ) a.Print(); while( !onepass( fixtures ) ) { Console.WriteLine( "Next pass" ); foreach( cours a in fixtures ) a.Print(); } } }

    HOWEVER!!  You need to understand that this will find A solution, but not necessarily the OPTIMUM solution.  This is a version of the "travelling salesman" problem.  You would have to try all possible arrangements to find the subset with the most possible credits.


    Tim Roberts, Driver MVP Providenza & Boekelheide, Inc.

    Thursday, May 10, 2018 9:45 PM
  • If you want some LINQ, check this fragment:

    List<cours> result = new List<cours>();
    
    Func<cours, cours, bool> is_overlap =
        ( c1, c2 ) =>
            ( c1.beginTime >= c2.beginTime && c1.beginTime <= c2.endTime ) ||
            ( c1.endTime >= c2.beginTime && c1.endTime <= c2.endTime ) ||
            ( c2.beginTime >= c1.beginTime && c2.beginTime <= c1.endTime ) ||
            ( c2.endTime >= c1.beginTime && c2.endTime <= c1.endTime );
    
    var e = fixtures.OrderByDescending( f => f.credit ).AsEnumerable();
    
    while( e.Any() )
    {
        var c = e.First();
        result.Add( c );
        e = e.Skip( 1 ).Where( f => ! is_overlap( c, f ) ).ToList();
    }

    • Marked as answer by zydjohn Friday, May 11, 2018 1:56 PM
    Friday, May 11, 2018 5:27 AM
  • Hi zydjohn,

    Thank you for posting here.

    Alternative, you can sort the list by endTime values , then use loops to check overlap via comparing endTime with beginTime. you can treat it as timeline to figure out it.

    Here is a simple way for your reference.

    class Program
        {
            public class cours
            {
                public int coursID { get; set; }
                public DateTime beginTime { get; set; }
                public DateTime endTime { get; set; }
                public int credit { get; set; }
                public void Print()
                {
                    Console.WriteLine("Course {0}, time {1} - {2}, {3} credits",
                        coursID, beginTime, endTime, credit
                    );
                }
            }
            static void Main(string[] args)
            {
                #region Add fixture item
                List<cours> fixtures = new List<cours>();
                fixtures.Add(new cours
                {
                    coursID = 1,
                    beginTime = DateTime.Today.AddHours(33.0),
                    endTime = DateTime.Today.AddHours(35.0),
                    credit = 5
                });
     
                fixtures.Add(new cours
                {
                    coursID = 2,
                    beginTime = DateTime.Today.AddHours(34.0),
                    endTime = DateTime.Today.AddHours(36.0),
                    credit = 10
                });
     
                fixtures.Add(new cours
                {
                    coursID = 3,
                    beginTime = DateTime.Today.AddHours(37.0),
                    endTime = DateTime.Today.AddHours(39.0),
                    credit = 5
                });
     
                fixtures.Add(new cours
                {
                    coursID = 4,
                    beginTime = DateTime.Today.AddHours(40.0),
                    endTime = DateTime.Today.AddHours(42.0),
                    credit = 10
                });
                #endregion
     
                Console.WriteLine("original:");
                PrintItem(fixtures);
     
                Console.WriteLine("filtered:");
                //sort fixture by endTime.
                fixtures.OrderBy(g => g.endTime);
                while(!CheckOverlap(fixtures))
                {
                    PrintItem(fixtures);
                }
              
                Console.ReadKey();
     
            }
     
            static void PrintItem(List<cours> fixtures)
            {
                foreach (var item in fixtures)
                {
                    item.Print();
                }
            }
            static bool CheckOverlap(List<cours> fixtures)
            {
                foreach (cours a in fixtures)
                {
                    foreach (cours b in fixtures)
                    {
                        if (a.coursID >= b.coursID)
                            continue;
                        // Check for overlap.
                        if (a.endTime > b.beginTime)
                        {
                            if (a.credit > b.credit)
                                fixtures.Remove(b);
                            else
                                fixtures.Remove(a);
                            return false;
                        }
                    }
                }
                return true;
            }
        }
    

    Best Regards,

    Wendy


    MSDN Community Support
    Please remember to click "Mark as Answer" the responses that resolved your issue, and to click "Unmark as Answer" if not. This can be beneficial to other community members reading this thread. If you have any compliments or complaints to MSDN Support, feel free to contact MSDNFSF@microsoft.com.

    Friday, May 11, 2018 7:58 AM
    Moderator
  • Hello, Viorel:

    Thank you very much, your code works.  However, since I am new to C#, there is something is not easy to understand.

    Can you explain a little more about this statement:

    e = e.Skip( 1 ).Where( f => ! is_overlap( c, f ) ).ToList();

    Thanks,

    Friday, May 11, 2018 8:06 AM
  • Hi,

    Your code is easy to understand, and thanks for your good graph.  However, I think the LINQ solution seems to be more elegant, but not easy to understand.

    I think your way of detecting overlap is better: 

    if (a.endTime > b.beginTime)

    I want to find how to improve the LINQ solution using your way to detect the overlap.

    Thanks,

    Friday, May 11, 2018 9:00 AM
  • [...]

    Can you explain a little more about this statement:

    e = e.Skip( 1 ).Where( f => ! is_overlap( c, f ) ).ToList();




    The variable e is a list that contains the courses, sorted by Credit in descending order. First gets the first element, i.e. the course that has the highest Credit. Obviously, this course will be never discarded, therefore it is added to the results. Then Skip(1) bypasses this first element, and Where examines the rest of the courses and keeps only those that are not overlapped with the first course. Then ToList makes a list with kept ordered courses, and while continue the process until there are no more courses.

    The is_overlap function considers various possible cases, but you can simplify it if some of the cases are impractical.




    • Edited by Viorel_MVP Friday, May 11, 2018 10:08 AM
    Friday, May 11, 2018 10:06 AM
  • Hello, Viorel:

    Thank you very much for your code and good explanation.

    Now I understand better.

    Thanks again!

    Friday, May 11, 2018 1:57 PM
  • I'm micro-optimizing here, but it's not necessary to do all four comparisons.  All you have to check for is "does class c1 begin during c2", and "does class c2 begin during c1", which is the first and third line of your lambda.  Draw it on a whiteboard to convince yourself of that.

    Also, I want to re-emphasize to the original poster that, although this code will find **A** solution, it will not necessarily find the **BEST** solution.  Consider, for example:

    class 1, start 8, end 15, credits 3
    class 2, start 9, end 10, credits 2
    class 3, start 11, end 12, credits 2
    class 4, start 13, end 14, credits 2
    class 5, start 16, end 17, credits 2

    The solution Viorel posted (and the solution I posted) will both end up with classes 1 and 5, for a total of 5 credits.  But if you choose classes 2, 3, 4, and 5, you also get no overlaps, and you total 8 credits.


    Tim Roberts, Driver MVP Providenza & Boekelheide, Inc.

    Friday, May 11, 2018 9:57 PM