在原文《12306出票算法随想（一）》基础上，将递归改为了迭代算法，然后加了个简单的锁而已。
using System;
using System.Collections.Concurrent;
using System.Collections.Generic;
using System.Diagnostics.Contracts;
using System.Linq;
using System.Threading;namespace Ticket {public static class Program {public static void Main() {var train = new Train(100);var line = new Line(new List<Station> {new Station("A", TimeSpan.Parse("1:00"), TimeSpan.Parse("1:00")),new Station("B", TimeSpan.Parse("2:00"), TimeSpan.Parse("2:05")),new Station("C", TimeSpan.Parse("3:00"), TimeSpan.Parse("3:10")),new Station("D", TimeSpan.Parse("4:00"), TimeSpan.Parse("4:06")),new Station("E", TimeSpan.Parse("5:00"), TimeSpan.Parse("5:00"))});var booking = new Booking(line, train);var watcher = new Watcher(booking);Console.Write("Line route[interval]: ");foreach (var station in booking.Line.Stations)Console.Write($"{station.Name} -> ");Console.WriteLine($"[{booking.Intervals.Count}]");try {booking.Sell(0, 1, 36);booking.Sell(0, 2, 4);booking.Sell(0, 3, 6);booking.Sell(0, 4, 32);booking.Sell(1, 2, 27);booking.Sell(1, 4, 11);booking.Sell(3, 4, 12);Console.WriteLine("Sold at this moment:");Console.WriteLine(booking.ToString());Console.WriteLine("Available at this moment:");foreach (var interval in booking.Intervals) {Console.Write(" {0}{1}[{2}]",booking.Line.Stations[interval.Item1].Name,booking.Line.Stations[interval.Item2].Name,booking.Available(interval.Item1, interval.Item2));}Console.WriteLine();watcher.RunTrain();}catch (ArgumentOutOfRangeException e) {Console.WriteLine(e.Message);}}}internal class Station {public Station(string name, TimeSpan arrival, TimeSpan depart) {Contract.Requires(arrival <= depart);Name = name;Arrival = arrival;Depart = depart;}public string Name { get; }public TimeSpan Arrival { get; }public TimeSpan Depart { get; }public bool Before(Station that) => Depart < that.Arrival;public bool After(Station that) => Arrival > that.Depart;}internal class Line {public Line(IList<Station> stations) {Contract.Requires(stations.Count >= 2);Stations = stations;}public IList<Station> Stations { get; }}internal class Train {private readonly object _lock = new object();private int _load;public Train(int capacity) {Contract.Requires(capacity > 0);Capacity = capacity;_load = 0;}public int Capacity { get; }public int Load {get {lock (_lock) {return _load;}}}public int Board(int amount) {lock (_lock) {_load += amount;if (_load > Capacity)throw new ArgumentOutOfRangeException(nameof(amount), "Train is overloading.");return amount;}}public int Land(int amount) {lock (_lock) {_load -= amount;if (_load < 0)throw new ArgumentOutOfRangeException(nameof(amount), "Train loading should not be negative.");return amount;}}}internal class Booking {public Line Line { get; }public Train Train { get; }public IList<Tuple<int, int>> Intervals { get; } = new List<Tuple<int, int>>();private ConcurrentDictionary<Tuple<int, int>, int> Sold { get; } = new ConcurrentDictionary<Tuple<int, int>, int>();private readonly object _lock = new object();private int[] _loadingCache;private int[] _beginWithCache;private int[] _endWithCache;public Booking(Line line, Train train) {Line = line;Train = train;GenerateIntervals();ResetSold();_loadingCache = new int[Line.Stations.Count];_beginWithCache = new int[Line.Stations.Count];_endWithCache = new int[Line.Stations.Count];UpdateLoadingCache();}public void Sell(int begin, int end, int amount) {Contract.Requires(begin < end);Contract.Requires(amount > 0);var key = new Tuple<int, int>(begin, end);Sold.AddOrUpdate(key, amount, (k, v) => v + amount);lock (_lock) {UpdateLoadingCache();}}public int BeginWith(int station) {return _beginWithCache[station];}public int EndWith(int station) {return _endWithCache[station];}private void UpdateLoadingCache() {if (_loadingCache == null || _loadingCache.Length != Line.Stations.Count) {_loadingCache = new int[Line.Stations.Count];_beginWithCache = new int[Line.Stations.Count];_endWithCache = new int[Line.Stations.Count];}// 预计算每个站点的上车和下车人数Array.Clear(_beginWithCache, 0, _beginWithCache.Length);Array.Clear(_endWithCache, 0, _endWithCache.Length);foreach (var kvp in Sold) {var interval = kvp.Key;var amount = kvp.Value;_beginWithCache[interval.Item1] += amount;_endWithCache[interval.Item2] += amount;}// 计算每个站点的负载_loadingCache[0] = _beginWithCache[0];for (var station = 1; station < Line.Stations.Count; station++) {_loadingCache[station] = _loadingCache[station - 1] - _endWithCache[station] + _beginWithCache[station];}}private int LoadingAt(int station) {return _loadingCache[station];}public int Available(int begin, int end) {Contract.Requires(begin < end);var maxloading = 0;for (var station = begin; station < end; station++)maxloading = Math.Max(maxloading, LoadingAt(station));return Train.Capacity - maxloading;}private void GenerateIntervals() {Intervals.Clear();for (var begin = 0; begin < Line.Stations.Count - 1; begin++) {for (var end = begin + 1; end < Line.Stations.Count; end++)Intervals.Add(new Tuple<int, int>(begin, end));}}private void ResetSold() {Sold.Clear();foreach (var interval in Intervals)Sold.TryAdd(interval, 0);lock (_lock) {UpdateLoadingCache();}}public override string ToString() {return Intervals.Aggregate(string.Empty, (current, interval) =>current +$" {Line.Stations[interval.Item1].Name}{Line.Stations[interval.Item2].Name}[{Sold.GetOrAdd(interval, 0)}]");}}internal class Watcher {public Watcher(Booking booking) {Booking = booking;}private Booking Booking { get; }public void RunTrain() {for (var station = 0; station < Booking.Line.Stations.Count; station++) {Console.Write("Train arrived [{0}]:", Booking.Line.Stations[station].Name);Console.WriteLine(" -{0,3}, +{1,3} = {2}",Booking.Train.Land(Booking.EndWith(station)),Booking.Train.Board(Booking.BeginWith(station)),Booking.Train.Load);}}}
}