Codility - MaxNonOverlappingSegments  

by ne on 2022-09-05 under Algo/DS/Problems tagged with codility

The problem belongs to Codility, here is the link to the problem

Following code segment contains the description in the class comments, followed by fully working solution, then a brief detail about the solution afterwards

 

 



/**
 * Two arrays are given, for each i, A[i] represents the start of a segment and B[i] represents the end of the segment. Segments are sorted by their ends.
 * Two segments will be considered overlapping if they share atleast one common point, we want to return the size of a set which contains maximal number of non-overlapping segments.
 * For example : A = {1,3,7,9,9} and B = {5,6,8,9,10}. Maximal number of segments in any set is 3. A set of 4 non-overlapping segments is not possible.
 * So, answer: 3.
 */
public class MaxNonOverlappingSegments {

    public int solution(int[] A, int[] B) {
        if (A == null || A.length == 0) return 0;
        int prev_end=B[0];
        int max=1;
        for(int i=1;i < A.length;i++){
            if(A[i] > prev_end){
                max++;
                prev_end = B[i];
            }
        }
        return max;
    }

    public static void main(String[] args) {
        System.out.println(new MaxNonOverlappingSegments().solution(new int[]{1, 3, 7, 9, 9}, new int[]{5, 6, 8, 9, 10})); //3
    }
}



 

The complexity here is O(N). The solution is fully acceptable with score of 100% in codility.

 

The idea is to use a greedy approach and start from 1 segment. Whenever we encounter an non-overlapping segment we increase the max count and update the prev-end to the current segment.