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)

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