CSharpCodingChallenges_CodeWars/4kyu_Sum_of_Intervals.cs at master · SergeyFM/CSharpCodingChallenges_CodeWars · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
using System.Linq;
using Interval = System.ValueTuple<int, int>;

namespace CodingChallenges;
[TestClass]
public class _4kyu_Sum_of_Intervals {

    /*

    Sum of Intervals

    Write a function called sumIntervals/sum_intervals that accepts an array of intervals,
    and returns the sum of all the interval lengths. Overlapping intervals should only be counted once.

    Intervals
    Intervals are represented by a pair of integers in the form of an array. The first value of the interval
    will always be less than the second value. Interval example:
    [1, 5] is an interval from 1 to 5. The length of this interval is 4.

    Overlapping Intervals
    List containing overlapping intervals:

    [
       [1, 4],
       [7, 10],
       [3, 5]
    ]
    The sum of the lengths of these intervals is 7. Since [1, 4] and [3, 5] overlap,
    we can treat the interval as [1, 5], which has a length of 4.

    Examples:
    sumIntervals( [
       [1, 2],
       [6, 10],
       [11, 15]
    ] ) => 9

    sumIntervals( [
       [1, 4],
       [7, 10],
       [3, 5]
    ] ) => 7

    sumIntervals( [
       [1, 5],
       [10, 20],
       [1, 6],
       [16, 19],
       [5, 11]
    ] ) => 19

    sumIntervals( [
       [0, 20],
       [-100000000, 10],
       [30, 40]
    ] ) => 100000030
    Tests with large intervals
    Your algorithm should be able to handle large intervals.
    All tested intervals are subsets of the range [-1000000000, 1000000000].

    */

    [TestMethod]
    public void Test() {
        Assert.AreEqual(0, SumIntervals(new Interval[] { }));
        Assert.AreEqual(0, SumIntervals(new Interval[] { (4, 4), (6, 6), (8, 8) }));
        Assert.AreEqual(9, SumIntervals(new Interval[] { (1, 2), (6, 10), (11, 15) }));
        Assert.AreEqual(11, SumIntervals(new Interval[] { (4, 8), (9, 10), (15, 21) }));
        Assert.AreEqual(7, SumIntervals(new Interval[] { (-1, 4), (-5, -3) }));
        Assert.AreEqual(78, SumIntervals(new Interval[] { (-245, -218), (-194, -179), (-155, -119) }));
        Assert.AreEqual(54, SumIntervals(new Interval[] { (1, 2), (2, 6), (6, 55) }));
        Assert.AreEqual(23, SumIntervals(new Interval[] { (-2, -1), (-1, 0), (0, 21) }));
        Assert.AreEqual(7, SumIntervals(new Interval[] { (1, 4), (7, 10), (3, 5) }));
        Assert.AreEqual(6, SumIntervals(new Interval[] { (5, 8), (3, 6), (1, 2) }));
        Assert.AreEqual(19, SumIntervals(new Interval[] { (1, 5), (10, 20), (1, 6), (16, 19), (5, 11) }));
        Assert.AreEqual(13, SumIntervals(new Interval[] { (2, 5), (-1, 2), (-40, -35), (6, 8) }));
        Assert.AreEqual(1234, SumIntervals(new Interval[] { (-7, 8), (-2, 10), (5, 15), (2000, 3150), (-5400, -5338) }));
        Assert.AreEqual(158, SumIntervals(new Interval[] { (-101, 24), (-35, 27), (27, 53), (-105, 20), (-36, 26) }));
        Assert.AreEqual(2_000_000_000, SumIntervals(new Interval[] { (-1_000_000_000, 1_000_000_000) }));
        Assert.AreEqual(100_000_030, SumIntervals(new Interval[] { (0, 20), (-100_000_000, 10), (30, 40) }));

    }

    /*
    [
       [1, 4],
       [7, 10],
       [3, 5]
    ]
    The sum of the lengths of these intervals is 7. Since [1, 4] and [3, 5] overlap,
    we can treat the interval as [1, 5], which has a length of 4.

    sort by first
    [1, 4], [3, 5], [7, 10]
    for each
        if second < first second=first
        if second exists && second > next.first next.first=second
        sum += second-first

    */

    public static int SumIntervals((int, int)[] intervals) {

        Interval[] sortedIntervals = intervals.OrderBy(x => x.Item1).ToArray();
        int len = sortedIntervals.Length;
        int sum = 0;
        for (int i = 0; i < len; i++) {
            (int first, int second) = sortedIntervals[i];
            if (second < first) second = first;
            if (i < len - 1) {
                (int nextFirst, int nextSecond) = sortedIntervals[i + 1];
                if (second > nextFirst) sortedIntervals[i + 1].Item1 = second;
            }
            sum += second - first;
        }
        return sum;
    }

}