The power and simplicity of IComparer IV

IComparer is particularly interesting when dealing with multi-dimensional arrays. In this case, sorting a set of intervals can be tricky if done using standard merge sort or quick sort algorithms. IComparer makes the task super simple (sure behind the scenes it is using qSort, but the sorting function is very simplified in this case with IComparer). The merge of the intervals afterwards becomes a linear pass, and so is the calculation of the days without meetings. Code is down below, cheers, ACC.

Count Days Without Meetings - LeetCode

3169. Count Days Without Meetings

Medium

You are given a positive integer days representing the total number of days an employee is available for work (starting from day 1). You are also given a 2D array meetings of size n where, meetings[i] = [start_i, end_i] represents the starting and ending days of meeting i (inclusive).

Return the count of days when the employee is available for work but no meetings are scheduled.

Note: The meetings may overlap.

 

Example 1:

Input: days = 10, meetings = [[5,7],[1,3],[9,10]]

Output: 2

Explanation:

There is no meeting scheduled on the 4th and 8th days.

Example 2:

Input: days = 5, meetings = [[2,4],[1,3]]

Output: 1

Explanation:

There is no meeting scheduled on the 5th day.

Example 3:

Input: days = 6, meetings = [[1,6]]

Output: 0

Explanation:

Meetings are scheduled for all working days.

 

Constraints:

• 1 <= days <= 109
• 1 <= meetings.length <= 105
• meetings[i].length == 2
• 1 <= meetings[i][0] <= meetings[i][1] <= days

public class CountDaysComparer : IComparer
{
    public int Compare(Object x, Object y)
    {
        int[] pair1 = (int[])x;
        int[] pair2 = (int[])y;

        if (pair1[0] != pair2[0]) return pair1[0].CompareTo(pair2[0]);
        return pair1[1].CompareTo(pair2[1]);
    }
}

public List MergeDays(int[][] meetings)
{
    List retVal = new List();

    retVal.Add(meetings[0]);
    for (int i = 1; i < meetings.Length; i++)
    {
        if (meetings[i][0] > retVal[retVal.Count - 1][1]) retVal.Add(meetings[i]);
        else retVal[retVal.Count - 1][1] = Math.Max(retVal[retVal.Count - 1][1], meetings[i][1]);
    }

    return retVal;
}

public int CountDays(int days, int[][] meetings)
{
    Array.Sort(meetings, new CountDaysComparer());
    List mergedDays = MergeDays(meetings);

    int retVal = 0;
    retVal += (mergedDays[0][0] - 1);
    for (int i = 0; i < mergedDays.Count - 1; i++)
        retVal += (mergedDays[i + 1][0] - mergedDays[i][1]) > 0 ? mergedDays[i + 1][0] - mergedDays[i][1] - 1 : 0;
    retVal += (days - mergedDays[mergedDays.Count - 1][1]);

    return retVal;
}