##### Short Problem Definition:

Compute the total length covered by 1-dimensional segments.

##### Link

##### Complexity:

~~time complexity~~

~~space complexity~~

##### Execution:

I first create a numbers table from 1 to 1.000.000, this could be done just once when creating the DB. In this challenge it adds a flat 0.3sec runtime to all testcases.

In the second step I simply unique join the segments and number tables.

##### Solution:

-- create numbers utility structure, very basic integer primary key column n create table numbers(n integer not null, primary key(n asc)); -- insert generated sequential integers insert into numbers(n) select rowid from ( -- build 1,000,000 rows using Cartesian product select 1 from ( select 0 union select 1 union select 2 union select 3 union select 4 union select 5 union select 6 union select 7 union select 8 union select 9 ) a, ( select 0 union select 1 union select 2 union select 3 union select 4 union select 5 union select 6 union select 7 union select 8 union select 9 ) b, ( select 0 union select 1 union select 2 union select 3 union select 4 union select 5 union select 6 union select 7 union select 8 union select 9 ) c, ( select 0 union select 1 union select 2 union select 3 union select 4 union select 5 union select 6 union select 7 union select 8 union select 9 ) d, ( select 0 union select 1 union select 2 union select 3 union select 4 union select 5 union select 6 union select 7 union select 8 union select 9 ) e, ( select 0 union select 1 union select 2 union select 3 union select 4 union select 5 union select 6 union select 7 union select 8 union select 9 ) f ) derived; select count(distinct n) from numbers inner join segments on numbers.n between segments.l+1 and segments.r

If you enjoyed this post, then make sure you subscribe to my Newsletter and/or Feed.