Leetcode discuss: 56. Merge Intervals | C# Learning how to sort

Jan. 19, 2022

Introduction
It is the algorithm to sort intervals by start time first, and then end time next. The overlapped intervals should be considered carefully since I made a mistake and the failed test case reminded me the case, which is "the second interval is inside the first interval".

C# | SortedSet<int, int> | Sort the interval | How to merge
It is challenge for me to warmup the algorithm to prepare Microsoft onsite. I like to use SortedSet<Tuple<int,int>> to sort intervals, and also I like to write working code in less than 20 minutes.

I also like to see my growth in terms of problem solving, I like to write C# bug-free code without looking up how to define IComparer.

Failed test case | Learn a quick lesson
It is important for me to practice more algorithms in next month, so that I can perform better on onsite in Feb. 2022. Sometimes I should think about more carefully in terms of analysis.

[[1,4],[2,3]], output: [[1,3]], Expected: [[1,4]]
I changed the definition of end time for overlapped case using Math.Max(previous.Item2, current.Item2)))

The following code passes online judge.

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace Leetcode_56_merge_intervals
{
    class Program
    {
        static void Main(string[] args)
        {
            // intervals = [[1,3],[2,6],[8,10],[15,18]]
            // output: [[1,6],[8,10],[15,18]]
            var intervals = new int[4][];
            intervals[0] = new int[] {1, 3};
            intervals[1] = new int[] { 2, 6 };
            intervals[2] = new int[] { 8, 10 };
            intervals[3] = new int[] { 15, 18 };

            var result = Merge(intervals);
        }

        /// <summary>
        /// 56 merge intervals
        /// Using C# SortedSet<Tuple<start, end>> to sort all intervals using start time first, and then end time
        /// </summary>
        /// <param name="intervals"></param>
        /// <returns></returns>
        public static int[][] Merge(int[][] intervals)
        {
            if (intervals == null || intervals[0] == null || intervals[0].Length == 0)
                return new int[0][];

            var sorted = new SortedSet<Tuple<int, int>>();
            var list2 = new List<Tuple<int, int>>();
        
            foreach (var interval in intervals)
            {
                list2.Add(new Tuple<int, int>(interval[0], interval[1]));
                //sorted.Add(new Tuple<int, int>(interval[0], interval[1]));
            }
            
            sorted = new SortedSet<Tuple<int, int>>(list2); // sort once is better than SortedSet.Add one by one

            var list = sorted.ToList();

            var merged = new List<int[]>();

            var previous = (Tuple<int, int>)list[0];

            for (int i = 1; i < list.Count; i++)
            {
                var current = list[i];

                var overlapped = previous.Item2 >= current.Item1;
                if (overlapped)
                {
                    previous = new Tuple<int, int>(previous.Item1, Math.Max(previous.Item2, current.Item2)); // caught by online judge:[[1,4],[2,3]], output: [[1,3]], Expected: [[1,4]]
                }
                else
                {
                    merged.Add(new int[] { previous.Item1, previous.Item2 });
                    previous = new Tuple<int, int>(current.Item1, current.Item2);
                }
            }

            merged.Add(new int[] { previous.Item1, previous.Item2 });

            return merged.ToArray();
        }
    }
}

Follow up | what to learn using C# API | Leetcode discuss C#
Jan. 20, 2022
There are so many ways to apply sorting using C#. I spent near 30 minutes to go over Leetcode discuss and see what to learn from other.

1. Array.Sort | Apply rules of sorting, one or two levels;
2. LYNQ: Order clause, OrderBy, ThenBy, CompareTo, OrderBy, Aggregate
3. Comparer, or define a class to apply IComparer
4. SortedSet<Tuple<int, int>>
5. Others will be added later.

// 1. OrderBy clause
intervals = intervals.OrderBy(x => x[0]).ToArray();

// 2. List.Sort API
var input = new List<Interval>(intervals);
    if(isFirst){
        input.Sort((a, b) => ((Interval)a).start >= ((Interval)b).start ? 1 : -1);
    }
//3. Array.Sort 	
Array.Sort(intervals, (arr1, arr2) => arr1[0].CompareTo(arr2[0]));

// 4. OrderBy
intervals = intervals.OrderBy(x=> x[0]).ToArray();

// 5. Array.Sort
Array.Sort(intervals, (op1, op2) => op1[0].CompareTo(op2[0]));

// 6. Array.Sort
Array.Sort(intervals, (a,b) => a[0] - b[0]);

// 7. LYNQ OrderBy 
var sortedIntervals=intervals.ToList().OrderBy(x=>x[0]).ToList();

// 8. LYNQ OrderBy, Aggregate
return intervals.OrderBy(x => x.start).Aggregate(new List<Interval>(),

// 9. Array.Sort
Array.Sort(intervals,(x,y)=>{
            if(x[0]==y[0])
                return x[1].CompareTo(y[1]);
            else
                return x[0].CompareTo(y[0]);
        });
		
// 10. Array.Sort API and also Comparer class
Array.Sort(intervals, (x, y) => Comparer<int>.Default.Compare(x[0], y[0]));

// 11. Define class Comparer to implement IComparer interface
Array.Sort(intervals, new Comparer());
public class Comparer : IComparer  {
  int IComparer.Compare( object x, object y )  {
      return( ((int[])x)[0] - ((int[])y)[0]);
  }
}
// 12. Define class Interval, order by Start first, next order by End if needed
intervals = intervals.OrderBy(x => x.Start).ThenBy(x => x.End).ToList();
class Interval
{
    public readonly int Start;
    public readonly int End;
    
    public Interval(int start, int end)
    {
        Start = start;
        End = end;
    }
}

I will look into more carefully about C# sorting techniques in short future. I choose to use C# SortedSet<Tuple<int, int>> instead of using IComparer. C# System.Lynq is very good choice to write working code if I have time to learn more and practice more.