Hello folks!
So I know from personal experience, this is where the coding problems start to become a little more difficult!
Lets check out the following problem:
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].
As you can see, this challenge has quite the intro! As always I will paste this into ChatGPT whilst asking it to solve the probably whilst being as accurate as possible and not to make any mistakes.
Solving it in C
Attempt #1
#include <stdlib.h>
#include <stdbool.h>
struct interval {
int first;
int second;
};
int sum_intervals(const struct interval *v, size_t n)
{
const int MAX = 2000000000;
const int OFFSET = 1000000000;
// create a bitmap to store the coverage of each position
bool *coverage = calloc(MAX, sizeof(bool));
if (!coverage) {
return -1; // error: unable to allocate memory
}
// iterate over the intervals, setting their coverage in the bitmap
for (size_t i = 0; i < n; i++) {
int start = v[i].first + OFFSET;
int end = v[i].second + OFFSET;
for (int j = start; j < end; j++) {
coverage[j] = true;
}
}
// iterate over the bitmap, counting the covered positions
int count = 0;
for (int i = 0; i < MAX; i++) {
if (coverage[i]) {
count++;
}
}
// release the memory allocated for the coverage bitmap
free(coverage);
return count;
}
Attempt #2
#include <stdbool.h>
#include <stdlib.h>
struct interval {
int first;
int second;
};
int sum_intervals(const struct interval *v, size_t n)
{
const int MAX = 200000001;
bool *coverage = calloc(MAX, sizeof(bool));
if (!coverage) {
return -1; // error: unable to allocate memory
}
for (size_t i = 0; i < n; i++) {
int start = v[i].first + 100000000;
int end = v[i].second + 100000000;
for (int j = start; j < end; j++) {
coverage[j] = true;
}
}
int count = 0;
for (int i = 0; i < MAX; i++) {
if (coverage[i]) {
count++;
}
}
free(coverage);
return count;
}
Attempt #3
#include <stdbool.h>
#include <stdlib.h>
struct interval {
int first;
int second;
};
int sum_intervals(const struct interval *v, size_t n) {
// find the maximum and minimum values of the intervals
int max_val = v[0].second;
int min_val = v[0].first;
for (size_t i = 1; i < n; i++) {
if (v[i].second > max_val) {
max_val = v[i].second;
}
if (v[i].first < min_val) {
min_val = v[i].first;
}
}
// allocate an array to store the coverage of each position
bool *coverage = calloc(max_val - min_val, sizeof(bool));
if (!coverage) {
return -1; // error: unable to allocate memory
}
// iterate over the intervals, adding their coverage to the array
for (size_t i = 0; i < n; i++) {
int start = v[i].first;
int end = v[i].second;
for (int j = start - min_val; j < end - min_val; j++) {
coverage[j] = true;
}
}
// iterate over the array, counting the covered positions
int count = 0;
for (int i = 0; i < max_val - min_val; i++) {
if (coverage[i]) {
count++;
}
}
// release the memory allocated for the coverage array
free(coverage);
return count;
}
Sadly, ChatGPT was not able to solve this particular problem using C with the information I had provided.
Solving it in Haskell
Attempt #1
module SumOfIntervals (sumOfIntervals) where
import Data.List (sort)
sumOfIntervals :: [(Int, Int)] -> Int
sumOfIntervals xs = go $ sort $ concatMap (\(a, b) -> [a..b-1]) xs
where go [] = 0
go [x] = 1
go (x:y:xs)
| y == x+1 = go (y:xs)
| otherwise = 1 + go (y:xs)
Attempt #2
module SumOfIntervals (sumOfIntervals) where
import Data.List (sort)
sumOfIntervals :: [(Int, Int)] -> Int
sumOfIntervals intervals = sum $ map length $ mergeOverlapping intervals
mergeOverlapping :: [(Int, Int)] -> [(Int, Int)]
mergeOverlapping intervals = foldr merge [] (sort intervals)
where merge x [] = [x]
merge x ((y1,y2):ys) | x1 <= y2 = merge (y1,max x2 y2) ys
| otherwise = x:(y1,y2):ys
where (x1,x2) = x
Attempt #3
module SumOfIntervals (sumOfIntervals) where
import Data.List (sort)
sumOfIntervals :: [(Int, Int)] -> Int
sumOfIntervals = sum . map length . mergeOverlappingIntervals . sortIntervals
where
sortIntervals = sort . map sortInterval
sortInterval (x, y) = if x <= y then (x, y) else (y, x)
mergeOverlappingIntervals [] = []
mergeOverlappingIntervals [x] = [x]
mergeOverlappingIntervals ((x1, y1):(x2, y2):xs)
| y1 >= x2 = mergeOverlappingIntervals ((x1, max y1 y2):xs)
| otherwise = (x1, y1) : mergeOverlappingIntervals ((x2, y2):xs)
Again, sadly, ChatGPT was not able to solve this particular problem using Haskell with the information I had provided.
Time for our lord and saviour, JavaScript
Solving it in JavaScript
Attempt #1
function sumIntervals(intervals) {
// Initialize an empty array to store the merged intervals
let mergedIntervals = [];
// Sort the intervals by their start values
intervals.sort((a, b) => a[0] - b[0]);
// Merge the intervals
for (let i = 0; i < intervals.length; i++) {
let currentInterval = intervals[i];
// If the mergedIntervals array is empty or if the current interval doesn't overlap with the last interval in the array, add it to the mergedIntervals array
if (mergedIntervals.length === 0 || currentInterval[0] > mergedIntervals[mergedIntervals.length - 1][1]) {
mergedIntervals.push(currentInterval);
}
// If the current interval overlaps with the last interval in the mergedIntervals array, merge them by updating the end value of the last interval in the array
else if (currentInterval[1] > mergedIntervals[mergedIntervals.length - 1][1]) {
mergedIntervals[mergedIntervals.length - 1][1] = currentInterval[1];
}
}
// Calculate the sum of the interval lengths
let sum = 0;
for (let i = 0; i < mergedIntervals.length; i++) {
sum += mergedIntervals[i][1] - mergedIntervals[i][0];
}
return sum;
}
Would you Adam and Eve it, we have a first time solution with JavaScript! The above code passed without any issues or complications!
I truly thought this was going to be the last article in this series but we live to fight another day! Next time, rank 3 KYU.
Catch you then.
Top comments (0)