Test results - Codility

Tasks Details

hard

1. SqlSegmentsSum

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

your query should return 5, as the segments cover the part of the line from 1 to 6.

Solution

Programming language used SQL (SQLite)

Time spent on task 42 minutes

Notes

not defined yet

Code: 10:20:10 UTC, sql, verify, result: Passed

show code in pop-up

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47

SELECT ifnull(SUM(r-l),0) valor
FROM (
SELECT *
FROM
  (SELECT l,
    CASE
      WHEN l = minimo
      THEN
        CASE
          WHEN r = maximo
          THEN r
          ELSE
            (SELECT MIN(maximo)
            FROM
              (SELECT l,
                r,
                (SELECT MAX(id2.r) FROM segments id2 WHERE id1.l <= id2.r AND id1.r >= id2.l
                ) maximo
              FROM segments id1
             
              )
            WHERE r    = maximo
            AND maximo > seg1.r
            )
        END
      ELSE l
    END r,
    minimo, maximo
  FROM
    (SELECT *
    FROM
      (SELECT l,
        r,
        (SELECT MIN(id2.l) FROM segments id2 WHERE id1.l <= id2.r AND id1.r >= id2.l
        ) minimo,
        (SELECT MAX(id2.r) FROM segments id2 WHERE id1.l <= id2.r AND id1.r >= id2.l
        ) maximo
      FROM segments id1
   
      )
    WHERE l = minimo
    OR r    = maximo
    )seg1
    ) group by minimo, maximo, l, r
  )
  
  ;

Analysis

expand all Example tests

▶

example
example test

✔

0.226 s

Code: 10:24:03 UTC, sql, verify, result: Passed

show code in pop-up

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47

SELECT ifnull(SUM(r-l),0) valor
FROM (
SELECT *
FROM
  (SELECT l,
    CASE
      WHEN l = minimo
      THEN
        CASE
          WHEN r = maximo
          THEN r
          ELSE
            (SELECT MIN(maximo)
            FROM
              (SELECT l,
                r,
                (SELECT MAX(id2.r) FROM segments id2 WHERE id1.l <= id2.r AND id1.r >= id2.l
                ) maximo
              FROM segments id1
             
              )
            WHERE r    = maximo
            AND maximo > seg1.r
            )
        END
      ELSE l
    END r,
    minimo, maximo
  FROM
    (SELECT *
    FROM
      (SELECT l,
        r,
        (SELECT MIN(id2.l) FROM segments id2 WHERE id1.l <= id2.r AND id1.r >= id2.l
        ) minimo,
        (SELECT MAX(id2.r) FROM segments id2 WHERE id1.l <= id2.r AND id1.r >= id2.l
        ) maximo
      FROM segments id1
   
      )
    WHERE l = minimo
    OR r    = maximo
    )seg1
    ) group by minimo, maximo, l, r
  )
  
  ;

Analysis

expand all Example tests

▶

example
example test

✔

0.218 s

Code: 10:24:40 UTC, sql, verify, result: Passed

show code in pop-up

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47

SELECT ifnull(SUM(r-l),0) valor
FROM (
SELECT *
FROM
  (SELECT l,
    CASE
      WHEN l = minimo
      THEN
        CASE
          WHEN r = maximo
          THEN r
          ELSE
            (SELECT MIN(maximo)
            FROM
              (SELECT l,
                r,
                (SELECT MAX(id2.r) FROM segments id2 WHERE id1.l <= id2.r AND id1.r >= id2.l
                ) maximo
              FROM segments id1
             
              )
            WHERE r    = maximo
            AND maximo > seg1.r
            )
        END
      ELSE l
    END r,
    minimo, maximo
  FROM
    (SELECT *
    FROM
      (SELECT l,
        r,
        (SELECT MIN(id2.l) FROM segments id2 WHERE id1.l <= id2.r AND id1.r >= id2.l
        ) minimo,
        (SELECT MAX(id2.r) FROM segments id2 WHERE id1.l <= id2.r AND id1.r >= id2.l
        ) maximo
      FROM segments id1
   
      )
    WHERE l = minimo
    OR r    = maximo
    )seg1
    ) group by minimo, maximo, l, r
  )
  
  ;

Analysis

expand all Example tests

▶

example
example test

✔

0.265 s

Code: 10:41:59 UTC, sql, verify, result: Passed

show code in pop-up

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47

SELECT ifnull(SUM(r-l),0) valor
FROM (
SELECT *
FROM
  (SELECT l,
    CASE
      WHEN l = minimo
      THEN
        CASE
          WHEN r = maximo
          THEN r
          ELSE
            (SELECT MIN(maximo)
            FROM
              (SELECT l,
                r,
                (SELECT MAX(id2.r) FROM segments id2 WHERE id1.l <= id2.r AND id1.r >= id2.l
                ) maximo
              FROM segments id1
             
              )
            WHERE r    = maximo
            AND maximo > seg1.r
            )
        END
      ELSE l
    END r,
    minimo, maximo
  FROM
    (SELECT *
    FROM
      (SELECT l,
        r,
        (SELECT MIN(id2.l) FROM segments id2 WHERE id1.l <= id2.r AND id1.r >= id2.l
        ) minimo,
        (SELECT MAX(id2.r) FROM segments id2 WHERE id1.l <= id2.r AND id1.r >= id2.l
        ) maximo
      FROM segments id1
   
      )
    WHERE l = minimo
    OR r    = maximo
    )seg1
    ) group by minimo, maximo, l, r
  )
  
  ;

Analysis

expand all Example tests

▶

example
example test

✔

0.225 s

Code: 10:56:59 UTC, sql, verify, result: Passed

show code in pop-up

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47

SELECT ifnull(SUM(r-l),0) valor
FROM (
SELECT *
FROM
  (SELECT l,
    CASE
      WHEN l = minimo
      THEN
        CASE
          WHEN r = maximo
          THEN r
          ELSE
            (SELECT MIN(maximo)
            FROM
              (SELECT l,
                r,
                (SELECT MAX(id2.r) FROM segments id2 WHERE id1.l <= id2.r AND id1.r >= id2.l
                ) maximo
              FROM segments id1
             
              )
            WHERE r    = maximo
            AND maximo > seg1.r
            )
        END
      ELSE l
    END r,
    minimo, maximo
  FROM
    (SELECT *
    FROM
      (SELECT l,
        r,
        (SELECT MIN(id2.l) FROM segments id2 WHERE id1.l <= id2.r AND id1.r >= id2.l
        ) minimo,
        (SELECT MAX(id2.r) FROM segments id2 WHERE id1.l <= id2.r AND id1.r >= id2.l
        ) maximo
      FROM segments id1
   
      )
    WHERE l = minimo
    OR r    = maximo
    )seg1
    ) group by minimo, maximo, l, r
  )
  
  ;

Analysis

expand all Example tests

▶

example
example test

✔

0.224 s

Code: 10:57:02 UTC, sql, verify, result: Passed

show code in pop-up

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47

SELECT ifnull(SUM(r-l),0) valor
FROM (
SELECT *
FROM
  (SELECT l,
    CASE
      WHEN l = minimo
      THEN
        CASE
          WHEN r = maximo
          THEN r
          ELSE
            (SELECT MIN(maximo)
            FROM
              (SELECT l,
                r,
                (SELECT MAX(id2.r) FROM segments id2 WHERE id1.l <= id2.r AND id1.r >= id2.l
                ) maximo
              FROM segments id1
             
              )
            WHERE r    = maximo
            AND maximo > seg1.r
            )
        END
      ELSE l
    END r,
    minimo, maximo
  FROM
    (SELECT *
    FROM
      (SELECT l,
        r,
        (SELECT MIN(id2.l) FROM segments id2 WHERE id1.l <= id2.r AND id1.r >= id2.l
        ) minimo,
        (SELECT MAX(id2.r) FROM segments id2 WHERE id1.l <= id2.r AND id1.r >= id2.l
        ) maximo
      FROM segments id1
   
      )
    WHERE l = minimo
    OR r    = maximo
    )seg1
    ) group by minimo, maximo, l, r
  )
  
  ;

Analysis

expand all Example tests

▶

example
example test

✔

0.237 s

Code: 10:57:05 UTC, sql, final, score: 100

show code in pop-up

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47

SELECT ifnull(SUM(r-l),0) valor
FROM (
SELECT *
FROM
  (SELECT l,
    CASE
      WHEN l = minimo
      THEN
        CASE
          WHEN r = maximo
          THEN r
          ELSE
            (SELECT MIN(maximo)
            FROM
              (SELECT l,
                r,
                (SELECT MAX(id2.r) FROM segments id2 WHERE id1.l <= id2.r AND id1.r >= id2.l
                ) maximo
              FROM segments id1
             
              )
            WHERE r    = maximo
            AND maximo > seg1.r
            )
        END
      ELSE l
    END r,
    minimo, maximo
  FROM
    (SELECT *
    FROM
      (SELECT l,
        r,
        (SELECT MIN(id2.l) FROM segments id2 WHERE id1.l <= id2.r AND id1.r >= id2.l
        ) minimo,
        (SELECT MAX(id2.r) FROM segments id2 WHERE id1.l <= id2.r AND id1.r >= id2.l
        ) maximo
      FROM segments id1
   
      )
    WHERE l = minimo
    OR r    = maximo
    )seg1
    ) group by minimo, maximo, l, r
  )
  
  ;

Analysis summary

The solution obtained perfect score.

Analysis

expand all Example tests

▶

example
example test

✔

0.227 s

expand all Correctness tests

▶

simple1
[0,10],[20,30]

✔

0.226 s

▶

simple2
nested segments

✔

0.223 s

▶

simple3
disjoint segments

✔

0.246 s

▶

simple4
[(0,1),(0,2),(4,6),(8,11)]

✔

0.248 s

▶

simple5
[(0,2),(1,3),(5,10)]

✔

0.252 s

0.249 s

▶

simple6
nested segments with common left endpoints

✔

0.253 s

0.235 s

▶

staircase1
staircase

✔

0.226 s

▶

staircase2
forking segments

✔

0.226 s

▶

extreme_single
single segment [0,10]

✔

0.226 s

▶

extreme_empty
no segments

✔

0.224 s

▶

extreme_common_endpoints
[0,20], [0,3], [15,20]

✔

0.223 s

▶

large_disjoint_segments
1000 disjoint segments

✔

0.860 s

▶

large_staircase
1000 steps staircase

✔

0.558 s

▶

large_nested_segments
1000 nested segments

✔

0.231 s

▶

large_forking
forking segments

✔

0.239 s