Algorithms-UCSanDiego

Data Structures and Algorithms by UCSanDiego

View project on GitHub

5. Collecting Signatures

https://en.wikipedia.org/wiki/Greedy_algorithm

Problem

Solutions

C

    typedef int Type;
    typedef Type* HType;

    const Type INF = 1e9 + 1;

    typedef struct {
        Type a, b;
    } Segment;
    Segment createSegment( Type a, Type b ){
        Segment S;
        S.a = a;
        S.b = b;
        return S;
    }
    typedef Segment* HSegment;

    int comparator( const void* lhs, const void* rhs ){ // descending order of segment end-point b
        Segment first  = *( HSegment ) lhs,
                second = *( HSegment ) rhs;
        if( first.b == second.b )
            return( first.a < second.a )? 1 : -1;
        return( first.b < second.b )? 1 : -1;
    }

    void minPoints( HSegment cur, Type N, HType ans ){
        size_t w = 0; // (w)rite index into (ans)wer
        for( size_t i=0; i < N; ++i )
            ans[ i ] = INF;
        qsort( cur, N, sizeof( Segment ), comparator );
        for( Segment next[ N ]; 0 < N; ){
            Type B = cur[ N-1 ].b; // greedy choice: the smallest segment end-point b
            ans[ w++ ] = B;
            size_t x = 0; // write index into ne(x)t
            for( size_t i=0; i < N; ++i ) if( ! ( cur[ i ].a <= B && B <= cur[ i ].b )) // next is all (s)egments of cur which do NOT contain B
                next[ x++ ] = cur[ i ];
            N = x;
            for( int i=0; i< N; ++i )
                cur[ i ] = next[ i ];
        }
    }

    int main() {
        Type N = 0; scanf( "%d", &N );
        Segment S[ N ];
        for( Type i=0, a=0, b=0; i < N; ++i ){
            scanf( "%d %d", &a, &b );
            S[ i ] = createSegment( a, b );
        }
        Type ans[ N ];
        minPoints( S, N, ans );
        int x = 0;
        for(; ans[ x ] != INF; ++x ); // x is the first invalid index
        printf( "%d\n", x );
        for( size_t i=0; i < x; ++i )
            printf( "%d ", ans[ i ] );
        printf( "\n" );
        return 0;
    }

CPP

    #include <iostream>
    #include <iomanip>
    #include <vector>
    #include <algorithm>
    #include <iterator>

    using namespace std;

    using Type = int;
    struct Segment {
        Type a{ 0 }, b{ 0 };
        bool operator<( const Segment& rhs ) const {
            return ! ( b < rhs.b ); // descending order of segment end-point b
        }
    };
    ostream& operator<<( ostream& stream, const Segment& rhs ){
        stream << "{ " << rhs.a << "," << rhs.b << " }";
        return stream;
    }
    using Segments = vector< Segment >;

    class Solution {
    public:
        using Collection = vector< Type >;
        Collection minPoints( Segments& cur, Collection ans={} ){
            sort( cur.begin(), cur.end() );
            int trim = 0;
            for( Segments next; ! cur.empty(); swap( cur,next ), next.clear(), ++trim ){
                auto B = cur.back().b; // greedy choice: the smallest segment end-point b
                ans.emplace_back( B );
                cur.pop_back();
                for( auto s: cur ) if( ! ( s.a <= B && B <= s.b )) // next is all (s)egments of cur which do NOT contain B
                    next.emplace_back( s );
            }
            return ans;
        }
    };

    int main() {
        Type N{ 0 }; cin >> N;
        Segments S( N );
        for( int i{ 0 }; i < N; ++i ){
            Type a{ 0 }, b{ 0 }; cin >> a >> b;
            S[ i ] = { a,b };
        }
        Solution solution;
        auto ans = solution.minPoints( S );
        cout << ans.size() << endl;
        copy( ans.begin(), ans.end(), ostream_iterator< Type >( cout, " " ));
        cout << endl;
        return 0;
    }

Java

    import java.util.Scanner;
    import java.util.Arrays;

    public class Main {

        public static int INF = 1000000001;

        public static class Segment implements Comparable< Segment >{
            int a, b;
            Segment( int a, int b ){
                this.a = a;
                this.b = b;
            }
            public int compareTo( Segment rhs ){
                if( b == rhs.b )
                    return( a < rhs.a )? 1 : -1;
                return( b < rhs.b )? 1: -1;
            }
        }

        public static int[] minPoints( Segment[] cur, int N ){
            int w = 0; // (w)rite index into (ans)wer
            int[] ans = new int[ N ];
            for( int i=0; i < N; ++i )
                ans[ i ] = INF;
            Arrays.sort( cur );
            for( Segment[] next = new Segment[ N ]; 0 < N; ){
                int B = cur[ N-1 ].b; // greedy choice: the smallest segment end-point b
                ans[ w++ ] = B;
                int x = 0; // write index into ne(x)t
                for( int i=0; i < N; ++i ) if( ! ( cur[ i ].a <= B && B <= cur[ i ].b )) // next is all segments of cur which do NOT contain B
                    next[ x++ ] = cur[ i ];
                N = x;
                for( int i=0; i< N; ++i )
                    cur[ i ] = next[ i ];
            }
            return ans;
        }

        public static void main( String[] args ){
            Scanner input = new Scanner( System.in );
            int N = input.nextInt();
            Segment[] S = new Segment[ N ];
            for( int i=0, a=0, b=0; i < N; ++i ){
                a = input.nextInt();
                b = input.nextInt();
                S[ i ] = new Segment( a, b );
            }
            int[] ans = minPoints( S, N );
            int x = 0;
            for(; ans[ x ] != INF; ++x );
            System.out.println( x );
            for( int i=0; i < x; ++i )
                System.out.print( ans[ i ] + " " );
        }
    }

Python3

    from typing import List

    class Segment:
        a = 0
        b = 0

        def __init__( self, a, b ):
            self.a = a
            self.b = b

        def __lt__( self, rhs ): # descending order of segment end-point b
            if self.b == rhs.b:
                return True if self.a > rhs.a else False 
            return True if self.b > rhs.b else False

    class Solution:
        def minPoints( self, cur: List[int] ):
            ans = []
            cur.sort()
            while 0 < len( cur ):
                B = cur[ -1 ].b # greedy choice: the smallest segment end-point b
                ans.append( B )
                next = []
                for i in range( len( cur )):
                    if not ( cur[ i ].a <= B and B <= cur[ i ].b ): # next is all (s)egments of cur which do NOT contain B
                        next.append( cur[ i ] )
                cur = next
            return ans

    if __name__ == '__main__':
        solution = Solution()
        N = int( input() )
        S = []
        for _ in range( N ):
            a, b = map( int, input().split() )
            S.append( Segment( a,b ))
        ans = solution.minPoints( S )
        print( len( ans ))
        for x in ans:
            print( x, end=" " )