# 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()
```

{"mode":"full","isActive":false}

## 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();
}
}
```

{"mode":"full","isActive":false}

## 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;
}
}
```

{"mode":"full","isActive":false}

## 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** 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;
}
}

}

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

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

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

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

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

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

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

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 != '\0') { 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, "%d\n", result);
}

fclose(fptr);

return 0;
}

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] = '\0';
}

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;
}
```

{"mode":"full","isActive":false}