Tasks Details
easy
Find a maximal set of non-overlapping segments.
Task Score
100%
Correctness
100%
Performance
100%
Located on a line are N segments, numbered from 0 to N − 1, whose positions are given in arrays A and B. For each I (0 ≤ I < N) the position of segment I is from A[I] to B[I] (inclusive). The segments are sorted by their ends, which means that B[K] ≤ B[K + 1] for K such that 0 ≤ K < N − 1.
Two segments I and J, such that I ≠ J, are overlapping if they share at least one common point. In other words, A[I] ≤ A[J] ≤ B[I] or A[J] ≤ A[I] ≤ B[J].
We say that the set of segments is non-overlapping if it contains no two overlapping segments. The goal is to find the size of a non-overlapping set containing the maximal number of segments.
For example, consider arrays A, B such that:
A[0] = 1 B[0] = 5 A[1] = 3 B[1] = 6 A[2] = 7 B[2] = 8 A[3] = 9 B[3] = 9 A[4] = 9 B[4] = 10The segments are shown in the figure below.
The size of a non-overlapping set containing a maximal number of segments is 3. For example, possible sets are {0, 2, 3}, {0, 2, 4}, {1, 2, 3} or {1, 2, 4}. There is no non-overlapping set with four segments.
Write a function:
function solution(A, B);
that, given two arrays A and B consisting of N integers, returns the size of a non-overlapping set containing a maximal number of segments.
For example, given arrays A, B shown above, the function should return 3, as explained above.
Write an efficient algorithm for the following assumptions:
- N is an integer within the range [0..30,000];
- each element of arrays A and B is an integer within the range [0..1,000,000,000];
- A[I] ≤ B[I], for each I (0 ≤ I < N);
- B[K] ≤ B[K + 1], for each K (0 ≤ K < N − 1).
Copyright 2009–2025 by Codility Limited. All Rights Reserved. Unauthorized copying, publication or disclosure prohibited.
Solution
Programming language used JavaScript
Time spent on task 25 minutes
Notes
not defined yet
Code: 14:14:51 UTC,
java,
autosave
Analysis
expand all
Example tests
1.
0.072 s
RUNTIME ERROR,
tested program terminated with exit code 1
stderr:
Invalid result type, integer expected, 'undefined' found Perhaps you are missing a 'return'?
Analysis
expand all
Example tests
1.
0.068 s
WRONG ANSWER,
got 1 expected 3
Code: 14:20:51 UTC,
js,
verify,
result: Failed
Analysis
expand all
Example tests
1.
0.072 s
WRONG ANSWER,
got 1 expected 3
Code: 14:21:14 UTC,
js,
verify,
result: Failed
// you can write to stdout for debugging purposes, e.g.
// console.log('this is a debug message');
function solution(A, B) {
// write your code in JavaScript (Node.js 8.9.4)
if (A.length < 2) {
return A.length;
}
return 1
}
User test case 1:
[[], []]
User test case 2:
[[1], [1]]
Analysis
expand all
Example tests
1.
0.068 s
WRONG ANSWER,
got 1 expected 3
Code: 14:21:21 UTC,
js,
verify,
result: Failed
// you can write to stdout for debugging purposes, e.g.
// console.log('this is a debug message');
function solution(A, B) {
// write your code in JavaScript (Node.js 8.9.4)
if (A.length < 2) {
return A.length;
}
return 2
}
User test case 1:
[[], []]
User test case 2:
[[1], [1]]
Analysis
expand all
Example tests
1.
0.068 s
WRONG ANSWER,
got 2 expected 3
Code: 14:35:04 UTC,
js,
autosave
Code: 14:35:27 UTC,
js,
autosave
Code: 14:37:18 UTC,
js,
autosave
Code: 14:37:48 UTC,
js,
autosave
// you can write to stdout for debugging purposes, e.g.
// console.log('this is a debug message');
function solution(A, B) {
// write your code in JavaScript (Node.js 8.9.4)
if (A.length < 2) {
return A.length;
}
let count = 0;
let last = B[0];
for (let i = 1; i < A.length; i++) {
if (A[i] > last)
}
}
Code: 14:38:12 UTC,
js,
autosave
// you can write to stdout for debugging purposes, e.g.
// console.log('this is a debug message');
function solution(A, B) {
// write your code in JavaScript (Node.js 8.9.4)
if (A.length < 2) {
return A.length;
}
let count = 0;
let last = B[0];
for (let i = 1; i < A.length; i++) {
if (A[i] > last) {
count++;
last = B[i];
}
}
return count;
}
Code: 14:38:16 UTC,
js,
verify,
result: Passed
// you can write to stdout for debugging purposes, e.g.
// console.log('this is a debug message');
function solution(A, B) {
// write your code in JavaScript (Node.js 8.9.4)
if (A.length < 2) {
return A.length;
}
let count = 1;
let last = B[0];
for (let i = 1; i < A.length; i++) {
if (A[i] > last) {
count++;
last = B[i];
}
}
return count;
}
User test case 1:
[[], []]
User test case 2:
[[1], [1]]
Analysis
Code: 14:38:32 UTC,
js,
autosave
// you can write to stdout for debugging purposes, e.g.
// console.log('this is a debug message');
function solution(A, B) {
// write your code in JavaScript (Node.js 8.9.4)
if (A.length < 2) {
return A.length;
}
let count = 1;
let last = B[0];
for (let i = 1; i < A.length; i++) {
if (A[i] > last) {
count++;
last = B[i];
}
}
return count;
}
Code: 14:38:36 UTC,
js,
verify,
result: Passed
// you can write to stdout for debugging purposes, e.g.
// console.log('this is a debug message');
function solution(A, B) {
// write your code in JavaScript (Node.js 8.9.4)
if (A.length < 2) {
return A.length;
}
let count = 1;
let last = B[0];
for (let i = 1; i < A.length; i++) {
if (A[i] > last) {
count++;
last = B[i];
}
}
return count;
}
User test case 1:
[[], []]
User test case 2:
[[1], [1]]
User test case 3:
[[1, 1, 1, 1, 1], [1, 1, 1, 1, 1]]
Analysis
expand all
User tests
1.
0.068 s
OK
function result: 0
function result: 0
1.
0.068 s
OK
function result: 1
function result: 1
1.
0.072 s
OK
function result: 1
function result: 1
Code: 14:38:48 UTC,
js,
autosave
// you can write to stdout for debugging purposes, e.g.
// console.log('this is a debug message');
function solution(A, B) {
// write your code in JavaScript (Node.js 8.9.4)
if (A.length < 2) {
return A.length;
}
let count = 1;
let last = B[0];
for (let i = 1; i < A.length; i++) {
if (A[i] > last) {
count++;
last = B[i];
}
}
return count;
}
Code: 14:38:50 UTC,
js,
verify,
result: Passed
// you can write to stdout for debugging purposes, e.g.
// console.log('this is a debug message');
function solution(A, B) {
// write your code in JavaScript (Node.js 8.9.4)
if (A.length < 2) {
return A.length;
}
let count = 1;
let last = B[0];
for (let i = 1; i < A.length; i++) {
if (A[i] > last) {
count++;
last = B[i];
}
}
return count;
}
User test case 1:
[[], []]
User test case 2:
[[1], [1]]
User test case 3:
[[1, 1, 1, 1, 1], [1, 1, 1, 1, 1]]
User test case 4:
[[1, 1, 1, 2, 1], [1, 1, 1, 2, 1]]
Analysis
expand all
User tests
1.
0.068 s
OK
function result: 0
function result: 0
1.
0.068 s
OK
function result: 1
function result: 1
1.
0.068 s
OK
function result: 1
function result: 1
1.
0.068 s
OK
function result: 2
function result: 2
Code: 14:39:05 UTC,
js,
verify,
result: Passed
// you can write to stdout for debugging purposes, e.g.
// console.log('this is a debug message');
function solution(A, B) {
// write your code in JavaScript (Node.js 8.9.4)
if (A.length < 2) {
return A.length;
}
let count = 1;
let last = B[0];
for (let i = 1; i < A.length; i++) {
if (A[i] > last) {
count++;
last = B[i];
}
}
return count;
}
User test case 1:
[[], []]
User test case 2:
[[1], [1]]
User test case 3:
[[1, 1, 1, 1, 1], [1, 1, 1, 1, 1]]
User test case 4:
[[1, 1, 1, 2, 1], [1, 1, 1, 2, 1]]
User test case 5:
[[1, 2, 3, 4, 1], [1, 2, 3, 4, 1]]
Analysis
Code: 14:39:18 UTC,
js,
autosave
// you can write to stdout for debugging purposes, e.g.
// console.log('this is a debug message');
function solution(A, B) {
// write your code in JavaScript (Node.js 8.9.4)
if (A.length < 2) {
return A.length;
}
let count = 1;
let last = B[0];
for (let i = 1; i < A.length; i++) {
if (A[i] > last) {
count++;
last = B[i];
}
}
return count;
}
Code: 14:39:26 UTC,
js,
verify,
result: Passed
// you can write to stdout for debugging purposes, e.g.
// console.log('this is a debug message');
function solution(A, B) {
// write your code in JavaScript (Node.js 8.9.4)
if (A.length < 2) {
return A.length;
}
let count = 1;
let last = B[0];
for (let i = 1; i < A.length; i++) {
if (A[i] > last) {
count++;
last = B[i];
}
}
return count;
}
User test case 1:
[[], []]
User test case 2:
[[1], [1]]
User test case 3:
[[1, 1, 1, 1, 1], [1, 1, 1, 1, 1]]
User test case 4:
[[1, 1, 1, 2, 1], [1, 1, 1, 2, 1]]
User test case 5:
[[1, 2, 3, 4, 1], [1, 2, 3, 4, 1]]
User test case 6:
[[0, 0], [1, 2]]
Analysis
expand all
User tests
1.
0.068 s
OK
function result: 0
function result: 0
1.
0.068 s
OK
function result: 1
function result: 1
1.
0.068 s
OK
function result: 1
function result: 1
1.
0.068 s
OK
function result: 2
function result: 2
1.
0.068 s
OK
function result: 4
function result: 4
1.
0.068 s
OK
function result: 1
function result: 1
Code: 14:39:35 UTC,
js,
verify,
result: Passed
// you can write to stdout for debugging purposes, e.g.
// console.log('this is a debug message');
function solution(A, B) {
// write your code in JavaScript (Node.js 8.9.4)
if (A.length < 2) {
return A.length;
}
let count = 1;
let last = B[0];
for (let i = 1; i < A.length; i++) {
if (A[i] > last) {
count++;
last = B[i];
}
}
return count;
}
User test case 1:
[[], []]
User test case 2:
[[1], [1]]
User test case 3:
[[1, 1, 1, 1, 1], [1, 1, 1, 1, 1]]
User test case 4:
[[1, 1, 1, 2, 1], [1, 1, 1, 2, 1]]
User test case 5:
[[1, 2, 3, 4, 1], [1, 2, 3, 4, 1]]
User test case 6:
[[0, 0], [1, 2]]
Analysis
expand all
User tests
1.
0.072 s
OK
function result: 0
function result: 0
1.
0.072 s
OK
function result: 1
function result: 1
1.
0.072 s
OK
function result: 1
function result: 1
1.
0.072 s
OK
function result: 2
function result: 2
1.
0.072 s
OK
function result: 4
function result: 4
1.
0.072 s
OK
function result: 1
function result: 1
Code: 14:39:38 UTC,
js,
final,
score:
100
// you can write to stdout for debugging purposes, e.g.
// console.log('this is a debug message');
function solution(A, B) {
// write your code in JavaScript (Node.js 8.9.4)
if (A.length < 2) {
return A.length;
}
let count = 1;
let last = B[0];
for (let i = 1; i < A.length; i++) {
if (A[i] > last) {
count++;
last = B[i];
}
}
return count;
}
Analysis summary
The solution obtained perfect score.
Analysis
Detected time complexity:
O(N)
expand all
Correctness tests
1.
0.068 s
OK
2.
0.068 s
OK
1.
0.068 s
OK
1.
0.068 s
OK
2.
0.068 s
OK
1.
0.068 s
OK
2.
0.068 s
OK
1.
0.072 s
OK
expand all
Performance tests
1.
0.068 s
OK
1.
0.100 s
OK
2.
0.100 s
OK
1.
0.104 s
OK
1.
0.104 s
OK
1.
0.096 s
OK
2.
0.100 s
OK
3.
0.096 s
OK