Tasks Details
hard
Compute the total length covered by 1-dimensional segments.
Task Score
53%
Correctness
53%
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)
Time spent on task 37 minutes
Notes
not defined yet
Task timeline
Code: 10:25:26 UTC,
sql,
verify,
result: Passed
-- write your code in SQLite 3.8.6
SELECT total_length-total_overlap FROM (
SELECT sum(lengths) as total_length FROM (SELECT sum(r-l) as lengths FROM segments) as lengths) as total_length
,
(SELECT sum(diff) as total_overlap FROM (
SELECT
CASE
WHEN s2.l>=s1.r
THEN 0
WHEN s2.r<=s1.r
THEN s2.r-s2.l
ELSE s1.r-s2.l
END AS diff
FROM segments s1
JOIN segments s2
WHERE s2.l>s1.l OR (s2.l=s1.l AND s1.r>s2.r)
) as overlaps) as total_overlap;
Analysis
Code: 10:25:33 UTC,
sql,
verify,
result: Passed
-- write your code in SQLite 3.8.6
SELECT total_length-total_overlap FROM (
SELECT sum(lengths) as total_length FROM (SELECT sum(r-l) as lengths FROM segments) as lengths) as total_length
,
(SELECT sum(diff) as total_overlap FROM (
SELECT
CASE
WHEN s2.l>=s1.r
THEN 0
WHEN s2.r<=s1.r
THEN s2.r-s2.l
ELSE s1.r-s2.l
END AS diff
FROM segments s1
JOIN segments s2
WHERE s2.l>s1.l OR (s2.l=s1.l AND s1.r>s2.r)
) as overlaps) as total_overlap;
Analysis
Code: 10:25:36 UTC,
sql,
final,
score:
53
-- write your code in SQLite 3.8.6
SELECT total_length-total_overlap FROM (
SELECT sum(lengths) as total_length FROM (SELECT sum(r-l) as lengths FROM segments) as lengths) as total_length
,
(SELECT sum(diff) as total_overlap FROM (
SELECT
CASE
WHEN s2.l>=s1.r
THEN 0
WHEN s2.r<=s1.r
THEN s2.r-s2.l
ELSE s1.r-s2.l
END AS diff
FROM segments s1
JOIN segments s2
WHERE s2.l>s1.l OR (s2.l=s1.l AND s1.r>s2.r)
) as overlaps) as total_overlap;Analysis summary
The following issues have been detected: wrong answers, runtime errors.
Analysis
expand all
Correctness tests
1.
0.223 s
OK
1.
0.226 s
WRONG ANSWER,
got -10 expected 10
1.
0.224 s
OK
1.
0.223 s
OK
1.
0.224 s
OK
2.
0.223 s
OK
1.
0.229 s
WRONG ANSWER,
got 7 expected 9
2.
0.225 s
WRONG ANSWER,
got 7 expected 9
1.
0.223 s
OK
1.
0.225 s
WRONG ANSWER,
got 5 expected 9
1.
0.223 s
RUNTIME ERROR,
tested program terminated unexpectedly
stdout:
expected int, got NoneType
1.
0.225 s
RUNTIME ERROR,
tested program terminated unexpectedly
stdout:
expected int, got NoneType
1.
0.223 s
OK
1.
0.361 s
OK
1.
0.361 s
OK
1.
0.231 s
WRONG ANSWER,
got -9053200 expected 2000
1.
0.231 s
WRONG ANSWER,
got -1163 expected 729