# C# Clean O(N) time complexity with O(N) space

• I wrote a simple algorithm for this problem. Since we are merging with a list of intervals, we know that, at a minimum, the time complexity is O(N) regardless of the language to implement it. Now the O(N) space requirement is there so that we can return a new result rather than mutate the original list, and, more importantly, to keep the algorithm at O(N) time complexity. So we gave time complexity a higher priority than the space complexity. In C#, List.Remove has a O(N) time complexity on its own so we avoided the use of that. Finally, I believe the algorithm is pretty clean and understandable but comments are welcome.

``````/// <summary>
/// Given a set of non-overlapping intervals, insert a new interval into the intervals (merge if necessary).
/// You may assume that the intervals were initially sorted according to their start times.
/// </summary>
/// <example>
/// Given [1,2],[3,5],[6,7],[8,10],[12,16], insert and merge [4,9] in as [1,2],[3,10],[12,16].
/// This is because the new interval[4, 9] overlaps with[3, 5],[6,7],[8,10].
/// </example>
public class Solution
{
public IList<Interval> Insert(IList<Interval> intervals, Interval newInterval)
{
IList<Interval> result = new List<Interval>();
int length = intervals.Count;
bool merged = false;

//We are going to need to loop at least once
for (int i = 0; i < length; i++)
{
if (merged || newInterval.start > intervals[i].end)
{
}
else if(newInterval.end < intervals[i].start)
{
merged = true;
}
else
{
if(intervals[i].start < newInterval.start)
{
newInterval.start = intervals[i].start;
}
if(intervals[i].end > newInterval.end)
{
newInterval.end = intervals[i].end;
}
}
}

//Satifies condition when newInterval will be last interval
if (!merged)
{