HackerRank Interval Selection problem solution

In this HackerRank Interval Selection problem solution we have given a set of n intervals, find the size of its largest possible subset of intervals such that no three intervals in the subset share a common point.

Problem solution in Python.

#!/bin/python3

import math
import os
import random
import re
import sys

#
# Complete the 'intervalSelection' function below.
#
# The function is expected to return an INTEGER.
# The function accepts 2D_INTEGER_ARRAY intervals as parameter.
#

def intervalSelection(intervals):
    intervals.sort(key = lambda x : x[1])
    noOfSelections = 0
    busy = [[0, 0], [0, 0]]
    for interval in intervals:
        if interval[0] > busy[1][1]:
            noOfSelections += 1
            busy[1] = interval
        else: 
            if interval[0] > busy[0][1]:
                noOfSelections += 1
                busy[0] = interval
                if interval[1] > busy[1][1]:
                    (busy[0], busy[1]) = (busy[1], busy[0])
    return noOfSelections

if __name__ == '__main__':
    fptr = open(os.environ['OUTPUT_PATH'], 'w')

    s = int(input().strip())

    for s_itr in range(s):
        n = int(input().strip())

        intervals = []

        for _ in range(n):
            intervals.append(list(map(int, input().rstrip().split())))

        result = intervalSelection(intervals)

        fptr.write(str(result) + 'n')

    fptr.close()

Problem solution in Java.

import java.io.*;
import java.math.*;
import java.text.*;
import java.util.*;
import java.util.regex.*;

public class Solution {

    static int intervalSelection(int[][] intervals) {
        Arrays.sort(intervals, Comparator.comparing(interval -> interval[1]));

        int lastSingle = -1;
        int lastDouble = -1;

        int skipped = 0;
        
        for (int[] interval : intervals) {
            int start = interval[0];
            if (start <= lastDouble) {
                skipped++;
            } else if (start <= lastSingle) {
                lastDouble = lastSingle;
                lastSingle = interval[1];
            } else {
                lastSingle = interval[1];
            }
        }

        return intervals.length - skipped;
    }

    private static final Scanner scanner = new Scanner(System.in);

    public static void main(String[] args) throws IOException {
        BufferedWriter bufferedWriter = new BufferedWriter(new FileWriter(System.getenv("OUTPUT_PATH")));

        int s = Integer.parseInt(scanner.nextLine().trim());

        for (int sItr = 0; sItr < s; sItr++) {
            int n = Integer.parseInt(scanner.nextLine().trim());

            int[][] intervals = new int[n][2];

            for (int intervalsRowItr = 0; intervalsRowItr < n; intervalsRowItr++) {
                String[] intervalsRowItems = scanner.nextLine().split(" ");

                for (int intervalsColumnItr = 0; intervalsColumnItr < 2; intervalsColumnItr++) {
                    int intervalsItem = Integer.parseInt(intervalsRowItems[intervalsColumnItr].trim());
                    intervals[intervalsRowItr][intervalsColumnItr] = intervalsItem;
                }
            }

            int result = intervalSelection(intervals);

            bufferedWriter.write(String.valueOf(result));
            bufferedWriter.newLine();
        }

        bufferedWriter.close();
    }
}

Problem solution in C++.

#include<cstdio>
#include<iostream>
#include<cstring>
#include<vector>
#include<algorithm>

#define N 1009

using namespace std;

typedef pair<int,int> II;

int n;
II a[N];

int main()
{
    int T;
    cin>>T;
    while(T--)
    {
        cin>>n;
        for(int i=0;i<n;i++) cin>>a[i].second>>a[i].first;
        sort(a,a+n);
        int tot=0,p=0,pre=0;
        for(int i=0;i<n;i++)        
            if(a[i].second>p)
            {
                tot++;
                if(a[i].second<=pre) p=pre;
                pre=a[i].first;                
            }
        cout<<tot<<endl;    
    }
}

Problem solution in C.

#include <assert.h>
#include <limits.h>
#include <math.h>
#include <stdbool.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

char* readline();
char** split_string(char*);

struct interval{
    int begin;
    int end;
};

/*
 * Complete the intervalSelection function below.
 */
int intervalSelection(int n, struct interval *intervals) {
    if(n < 3){
        return n;
    }
    struct interval sortints[n];
    for(int i = 0; i < n; i++){
        sortints[i] = intervals[i];
        int curr = i;
        while(curr > 0){
            int next = (curr - 1)/2;
            if(sortints[next].begin < sortints[curr].begin){
                struct interval temp = sortints[curr];
                sortints[curr] = sortints[next];
                sortints[next] = temp;
                curr = next;
            }
            else{
                break;
            }
        }
    }

    for(int i = n - 1; i >= 0; i--){
        struct interval temp = sortints[0];
        sortints[0] = sortints[i];
        sortints[i] = temp;

        int curr = 0;
        while(true){
            int next = curr;
            if(2*curr + 1 < i && sortints[2*curr + 1].begin > sortints[next].begin){
                next = 2*curr + 1;
            }
            if(2*curr + 2 < i && sortints[2*curr + 2].begin > sortints[next].begin){
                next = 2*curr + 2;
            }
            if(next != curr){
                struct interval temp = sortints[curr];
                sortints[curr] = sortints[next];
                sortints[next] = temp;
                curr = next;
            }
            else{
                break;
            }
        }
    }


    //currend0 <= currend1 always
    int currend0 = (sortints[0].end < sortints[1].end? sortints[0].end : sortints[1].end);
    int currend1 = (sortints[0].end < sortints[1].end? sortints[1].end : sortints[0].end);
    int toreturn = 2;
    for(int i = 2; i < n; i++){
        struct interval currint = sortints[i];
        if(currint.begin > currend1){
            toreturn += 1;
            currend1 = currint.end;
        }
        else if(currint.begin > currend0){
            toreturn += 1;
            if(currint.end > currend1){
                currend0 = currend1;
                currend1 = currint.end;
            }
            else{
                currend0 = currint.end;
            }
        }
        else if(currint.end < currend0){
            currend1 = currend0;
            currend0 = currint.end;
        }
        else if(currint.end < currend1){
            currend1 = currint.end;
        }
    }

    return toreturn;
}

int main()
{
    FILE* fptr = fopen(getenv("OUTPUT_PATH"), "w");

    char* s_endptr;
    char* s_str = readline();
    int s = strtol(s_str, &s_endptr, 10);

    if (s_endptr == s_str || *s_endptr != '') { exit(EXIT_FAILURE); }

    for (int s_itr = 0; s_itr < s; s_itr++) {
        char* n_endptr;
        char* n_str = readline();
        int n = strtol(n_str, &n_endptr, 10);

        if (n_endptr == n_str || *n_endptr != '') { exit(EXIT_FAILURE); }

        struct interval *intervals = malloc(n * sizeof(struct interval));

        for (int intervals_row_itr = 0; intervals_row_itr < n; intervals_row_itr++) {

            char** intervals_item_temp = split_string(readline());

            for (int intervals_column_itr = 0; intervals_column_itr < 2; intervals_column_itr++) {
                char* intervals_item_endptr;
                char* intervals_item_str = intervals_item_temp[intervals_column_itr];
                int intervals_item = strtol(intervals_item_str, &intervals_item_endptr, 10);

                if (intervals_item_endptr == intervals_item_str || *intervals_item_endptr != '') { exit(EXIT_FAILURE); }

                if(intervals_column_itr == 0){
                    intervals[intervals_row_itr].begin = intervals_item;
                }
                else{
                    intervals[intervals_row_itr].end = intervals_item;
                }
            }
        }

        int result = intervalSelection(n, intervals);

        fprintf(fptr, "%dn", result);
    }

    fclose(fptr);

    return 0;
}

char* readline() {
    size_t alloc_length = 1024;
    size_t data_length = 0;
    char* data = malloc(alloc_length);

    while (true) {
        char* cursor = data + data_length;
        char* line = fgets(cursor, alloc_length - data_length, stdin);

        if (!line) { break; }

        data_length += strlen(cursor);

        if (data_length < alloc_length - 1 || data[data_length - 1] == 'n') { break; }

        size_t new_length = alloc_length << 1;
        data = realloc(data, new_length);

        if (!data) { break; }

        alloc_length = new_length;
    }

    if (data[data_length - 1] == 'n') {
        data[data_length - 1] = '';
    }

    data = realloc(data, data_length);

    return data;
}

char** split_string(char* str) {
    char** splits = NULL;
    char* token = strtok(str, " ");

    int spaces = 0;

    while (token) {
        splits = realloc(splits, sizeof(char*) * ++spaces);
        if (!splits) {
            return splits;
        }

        splits[spaces - 1] = token;

        token = strtok(NULL, " ");
    }

    return splits;
}