スイープラインアルゴリズムを使用してイベントの時間重複度の最大数を求める

はじめに

プログラミングにおいて、イベントのスケジューリングや予約システムなど、時間の重複をチェックする必要があるケースは多々あります。このような問題に対処する一つの効果的な方法は、スイープラインアルゴリズムを使用することです。この記事では、C#を用いてイベントの時間がどの程度重複しているかを検出し、その最大重複度を求める方法を解説します。

モデルクラスの定義

まず、イベントを表すための基本的なモデルクラスMyEventを定義します。このクラスには、イベントのID、開始時間、および終了時間を格納するプロパティが含まれます。

public class MyEvent
{
    public decimal Id { get; set; }
    public DateTime StartDate { get; set; }
    public DateTime EndDate { get; set; }
}

最大の重複度を求めるFindMaxOverlapのサンプルソースと解説

次に、MyEventクラスのインスタンスが格納されたリストから、開始時間と終了時間が重複しているイベントの最大数を求めるFindMaxOverlap関数を実装します。この関数では、イベントの開始を「+1」、終了を「-1」としてカウントし、スイープラインアルゴリズムを用いて全イベントを一度に処理します。

using System;
using System.Collections.Generic;
using System.Linq;

public static int FindMaxOverlap(List<MyEvent> events)
{
    var times = new List<(DateTime time, int type)>();
    foreach (var ev in events)
    {
        times.Add((ev.StartDate, 1)); // 開始時間
        times.Add((ev.EndDate, -1)); // 終了時間
    }

    times.Sort((a, b) => a.time.CompareTo(b.time));

    int maxOverlap = 0, currentOverlap = 0;
    foreach (var time in times)
    {
        currentOverlap += time.type;
        maxOverlap = Math.Max(maxOverlap, currentOverlap);
    }

    return maxOverlap;
}

この関数では、まずすべてのイベントの開始時刻と終了時刻をリストに追加し、それらを時刻でソートします。その後、リストを順に処理し、開始時刻に遭遇するたびにcurrentOverlapをインクリメントし、終了時刻に遭遇するたびにデクリメントします。このプロセスを通じて、maxOverlapに最大重複度を記録します。

呼び出し部分（main関数）の作成

最後に、FindMaxOverlap関数を呼び出し、その結果を出力するmain関数の実装例を示します。

class Program
{
    static void Main(string[] args)
    {
        List<MyEvent> events = new List<MyEvent>
        {
            // イベントのデータをここに追加
        };

        int maxOverlap = FindMaxOverlap(events);
        Console.WriteLine($"最大重複度: {maxOverlap}");
    }
}

この関数では、イベントのリストを作成し、FindMaxOverlap関数に渡して最大の重複度を計算します。計算された値はコンソールに出力されます。

まとめ

スイープラインアルゴリズムを使用することで、イベントの時間重複度を効率的に計算することが可能です。このアプローチは、時間順にイベントを処理することで、アルゴリズムの複雑さをO(n log n)に抑えることができます。