Tasks Details
hard
Compute the total length covered by 1-dimensional segments.
Task Score
100%
Correctness
100%
Performance
Not assessed
You are given a table segments with the following structure:
create table segments ( l integer not null, r integer not null, check(l <= r), unique(l,r) );Each record in this table represents a contiguous segment of a line, from l to r inclusive. Its length equals r − l.
Consider the parts of a line covered by the segments. Write an SQL query that returns the total length of all the parts of the line covered by the segments specified in the table segments. Please note that any parts of the line that are covered by several overlapping segments should be counted only once.
For example, given:
l | r --+-- 1 | 5 2 | 3 4 | 6your query should return 5, as the segments cover the part of the line from 1 to 6.
Copyright 2009–2024 by Codility Limited. All Rights Reserved. Unauthorized copying, publication or disclosure prohibited.
Solution
Programming language used SQL (SQLite)
Total time used 2 minutes
Effective time used 2 minutes
Notes
not defined yet
Task timeline
Code: 16:19:05 UTC,
sql,
verify,
result: Passed
-- write your code in SQLite 3.8.6
create table noncont (
a integer not null,
b integer not null
);
insert into noncont
select *
from segments s_out
where not exists (
select *
from segments s_in
where s_out.l>=s_in.l
and s_out.r<=s_in.r
and (s_out.r<>s_in.r or s_out.l<>s_in.l)
)
order by s_out.l asc;
select (
select IFNULL(sum(b-a),0)
from noncont
)
+
(
select IFNULL(sum(t2.a-t1.b),0)
from noncont t1,noncont t2
where t1.a<=t2.a
and (t1.b>=t2.a)
and (t1.a<>t2.a or t1.b<>t2.b)
and t2.a = (select min(t3.a)
from noncont t3
where t3.a>=t1.a
and (t3.a<>t1.a or t3.b<>t1.b)
)
);
Analysis
Code: 16:19:27 UTC,
sql,
verify,
result: Passed
-- write your code in SQLite 3.8.6
create table noncont (
a integer not null,
b integer not null
);
insert into noncont
select *
from segments s_out
where not exists (
select *
from segments s_in
where s_out.l>=s_in.l
and s_out.r<=s_in.r
and (s_out.r<>s_in.r or s_out.l<>s_in.l)
)
order by s_out.l asc;
select (
select IFNULL(sum(b-a),0)
from noncont
)
+
(
select IFNULL(sum(t2.a-t1.b),0)
from noncont t1,noncont t2
where t1.a<=t2.a
and (t1.b>=t2.a)
and (t1.a<>t2.a or t1.b<>t2.b)
and t2.a = (select min(t3.a)
from noncont t3
where t3.a>=t1.a
and (t3.a<>t1.a or t3.b<>t1.b)
)
);
Analysis
Code: 16:19:30 UTC,
sql,
final,
score: 
100
-- write your code in SQLite 3.8.6
create table noncont (
a integer not null,
b integer not null
);
insert into noncont
select *
from segments s_out
where not exists (
select *
from segments s_in
where s_out.l>=s_in.l
and s_out.r<=s_in.r
and (s_out.r<>s_in.r or s_out.l<>s_in.l)
)
order by s_out.l asc;
select (
select IFNULL(sum(b-a),0)
from noncont
)
+
(
select IFNULL(sum(t2.a-t1.b),0)
from noncont t1,noncont t2
where t1.a<=t2.a
and (t1.b>=t2.a)
and (t1.a<>t2.a or t1.b<>t2.b)
and t2.a = (select min(t3.a)
from noncont t3
where t3.a>=t1.a
and (t3.a<>t1.a or t3.b<>t1.b)
)
);
Analysis summary
The solution obtained perfect score.
Analysis
expand all
Correctness tests
1.
0.228 s
OK
1.
0.228 s
OK
1.
0.226 s
OK
1.
0.225 s
OK
1.
0.229 s
OK
2.
0.226 s
OK
1.
0.227 s
OK
2.
0.225 s
OK
1.
0.228 s
OK
1.
0.225 s
OK
1.
0.227 s
OK
1.
0.229 s
OK
1.
0.229 s
OK
1.
0.475 s
OK
1.
0.473 s
OK
1.
0.228 s
OK
1.
0.231 s
OK