[Codility] Lesson16 - Greedy algorithms: Max Nonoverlapping Segments

Problem

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] = 10

The 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:

class Solution { public int solution(int[] A, int[] 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, 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–2021 by Codility Limited. All Rights Reserved. Unauthorized copying, publication or disclosure prohibited.

app.codility.com/programmers/lessons/16-greedy_algorithms/max_nonoverlapping_segments/

MaxNonoverlappingSegments coding task - Learn to Code - Codility

How to solve

서로 겹치지 않는 선분을 조합해서 만들 수 있는 최대 선분 수 구하기!

A: 선분의 시작 지점

B: 선분의 끝 지점

 

Solution(c++)

// you can use includes, for example:
#include <bits/stdc++.h>

// you can write to stdout for debugging purposes, e.g.
// cout << "this is a debug message" << endl;

int solution(vector<int> &A, vector<int> &B) {
    // write your code in C++14 (g++ 6.2.0)
    int len = A.size();
    int count = 1;
    int end = B[0]; // initial end value
    if(len <1){
        return 0;
    }

    for(int i=1; i<len; i++){
        if(A[i] > end){
            count++;
            end = B[i];
        }
    }
    return count;
}

Test Result

app.codility.com/demo/results/training88FNFF-ABD/

Test results - Codility