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 | 6`

your 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 37 minutes

Effective time used 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