patterncsharpMinor

Finding overlapping time intervals

Submitted by: @import:stackexchange-codereview·Mar 10, 2026·

Viewed 0 times

intervalsoverlappingtimefinding

Problem

You have two lists with meetings scheduling (start time, end time). Meetings in single list don't intersect. Find all intersecting meetings across the two lists.

Is my complexity \$O(N M)\$? If I use binary search I might get \$O(N \log M)\$. Can you think of a better algorithm?

For simplicity, I didn't use DateTime. I just assumed meetings are in round hours.

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

namespace ConsoleApplication2
{

public class IntersectingMeetings
{
public IntersectingMeetings()
{
MeetingList meetingList1 = new MeetingList();
MeetingList meetingList2 = new MeetingList();
meetingList1.AddMeeting(2,3);
meetingList1.AddMeeting(1,2);

meetingList1.AddMeeting(4,6);

meetingList2.AddMeeting(2,3);
meetingList2.AddMeeting(3,4);
meetingList2.AddMeeting(5,6);
List intersectionsList = FindInterSections(meetingList1, meetingList2);
}

private List FindInterSections(MeetingList meetingList1,MeetingList meetingList2)
{
meetingList1.list.Sort();
meetingList2.list.Sort();
List intersectingList = new List();
foreach (var item in meetingList1.list)
{
foreach (var other in meetingList2.list)
{
if ((item.StartTime >= other.StartTime && item.EndTime =item.StartTime && other.EndTime list;
public MeetingList()
{
list = new List();
}
public void AddMeeting(int start, int end)
{
list.Add(new Meeting(start,end));
}
}

public class Meeting : IComparable
{
public int StartTime { set; get; }
public int EndTime { set; get; }

public Meeting(int start, int end)
{
StartTime = start;
EndTime = e

Solution

You could make the Meeting class generic with the T : IComparable constraint. Thus you'll be able to use any type as a time value:

[DebuggerDisplay("{Start} .. {End}")]
public sealed class Meeting
    where T : IComparable
{
    // You can replace these readonly fields with the auto-properties { get; private set; }:
    public readonly T Start;
    public readonly T End;

    public Meeting(T start, T end)
    {
        Start = start;
        End = end;
    }
}

Next you need a comparer:

public sealed class MeetingComparer : IEqualityComparer>
    where T : IComparable
{
    public bool Equals(Meeting x, Meeting y)
    {
        // We can use only 2 sequential comparisons to check for the intersection:
        return x.Start.CompareTo(y.Start) >= 0
            ? x.Start.CompareTo(y.End)  obj)
    {
        // Make all meetings have the same hash code.
        // In this case the Equals method will be called for each object.
        return 1;
    }
}

And finally you could use LINQ to find the intersecting meetings:

private static IEnumerable> FindIntersections(IEnumerable> list1,
    IEnumerable> list2)
    where T : IComparable
{
    return list1.Join(list2, p => p, p => p,
        (a, b) => new[] { a, b }, new MeetingComparer())
            .SelectMany(p => p);
}

Sample:

var list1 = new List>
                {
                    new Meeting(0, 1),
                    new Meeting(100, 111),
                    new Meeting(20, 41),
                    new Meeting(10, 11)
                };
var list2 = new List>
                {
                    new Meeting(2, 3),
                    new Meeting(105, 106),
                    new Meeting(40, 41),
                    new Meeting(15, 16)
                };

var intersection = FindIntersections(list1, list2);

EDIT

Try this code to find intersections of the sorted sets. It has complexity \$O(N+M)\$:

private static IEnumerable> FindIntersections(IEnumerable> listX,
    IEnumerable> listY)
    where T : IComparable
{
    var iteratorX = listX.GetEnumerator();
    var iteratorY = listY.GetEnumerator();
    Meeting lastX = null;
    Meeting lastY = null;
    iteratorX.MoveNext();
    iteratorY.MoveNext();
    while (iteratorX.Current != null && iteratorY.Current != null)
    {
        Meeting x = iteratorX.Current;
        Meeting y = iteratorY.Current;

        // Move iterators if needed:
        if (x.End.CompareTo(y.Start) = 0)
        {
            iteratorX.MoveNext();
        }
        else
        {
            iteratorY.MoveNext();
        }
    }
}

The method above:

Returns a set of the unique Meetings.

Supports case if one range overlaps several ranges in another set.

Code Snippets

[DebuggerDisplay("{Start} .. {End}")]
public sealed class Meeting<T>
    where T : IComparable<T>
{
    // You can replace these readonly fields with the auto-properties { get; private set; }:
    public readonly T Start;
    public readonly T End;

    public Meeting(T start, T end)
    {
        Start = start;
        End = end;
    }
}

public sealed class MeetingComparer<T> : IEqualityComparer<Meeting<T>>
    where T : IComparable<T>
{
    public bool Equals(Meeting<T> x, Meeting<T> y)
    {
        // We can use only 2 sequential comparisons to check for the intersection:
        return x.Start.CompareTo(y.Start) >= 0
            ? x.Start.CompareTo(y.End) <= 0
            : y.Start.CompareTo(x.End) <= 0;
    }

    public int GetHashCode(Meeting<T> obj)
    {
        // Make all meetings have the same hash code.
        // In this case the Equals method will be called for each object.
        return 1;
    }
}

private static IEnumerable<Meeting<T>> FindIntersections<T>(IEnumerable<Meeting<T>> list1,
    IEnumerable<Meeting<T>> list2)
    where T : IComparable<T>
{
    return list1.Join(list2, p => p, p => p,
        (a, b) => new[] { a, b }, new MeetingComparer<T>())
            .SelectMany(p => p);
}

var list1 = new List<Meeting<int>>
                {
                    new Meeting<int>(0, 1),
                    new Meeting<int>(100, 111),
                    new Meeting<int>(20, 41),
                    new Meeting<int>(10, 11)
                };
var list2 = new List<Meeting<int>>
                {
                    new Meeting<int>(2, 3),
                    new Meeting<int>(105, 106),
                    new Meeting<int>(40, 41),
                    new Meeting<int>(15, 16)
                };

var intersection = FindIntersections(list1, list2);

private static IEnumerable<Meeting<T>> FindIntersections<T>(IEnumerable<Meeting<T>> listX,
    IEnumerable<Meeting<T>> listY)
    where T : IComparable<T>
{
    var iteratorX = listX.GetEnumerator();
    var iteratorY = listY.GetEnumerator();
    Meeting<T> lastX = null;
    Meeting<T> lastY = null;
    iteratorX.MoveNext();
    iteratorY.MoveNext();
    while (iteratorX.Current != null && iteratorY.Current != null)
    {
        Meeting<T> x = iteratorX.Current;
        Meeting<T> y = iteratorY.Current;

        // Move iterators if needed:
        if (x.End.CompareTo(y.Start) < 0)
        {
            iteratorX.MoveNext();
            continue;
        }
        if (y.End.CompareTo(x.Start) < 0)
        {
            iteratorY.MoveNext();
            continue;
        }

        // Add items to the resulting set, if the items aren't already there:
        if (lastX != x)
        {
            yield return x;
            lastX = x;
        }
        if (lastY != y)
        {
            yield return y;
            lastY = y;
        }

        // Determine which iterator should be moved first:
        if (y.End.CompareTo(x.End) >= 0)
        {
            iteratorX.MoveNext();
        }
        else
        {
            iteratorY.MoveNext();
        }
    }
}

Context

StackExchange Code Review Q#71896, answer score: 8

Revisions (0)

No revisions yet.