HackerRank Interval Selection Problem Solution

In this post, we will solve HackerRank Interval Selection Problem Solution.

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.
Input Format
The first line contains an integer, s, denoting the number of interval sets you must find answers for. The s. (n + 1) subsequent lines describe each of the s interval sets as follows:

The first line contains an integer, n. denoting the number of intervals in the list. 2. Each line i of the n subsequent lines contains two space-separated integers describing
the respective starting (ai) and ending (bi) boundaries of an interval.

Output Format
For each of the s interval sets, print an integer denoting the size of the largest possible subset of intervals in the given set such that no three points in the subset overlap.

Sample Input

Sample Output

Explanation
For set so, all three intervals fall on point 2 so we can only choose any 2 of the intervals,
Thus, we print 2 on a new line.
For set $1, all three intervals span the range from 1 to 5 so we can only choose any 2 of them. Thus, we print 2 on a new line.
For set $2, we can choose all 4 intervals without having more than two of them overlap at any given point. Thus, we print 4 on a new line.
For set 83, the intervals [1, 10], [1, 3], and [3, 6] all overlap at point 3, so we must only choose 2 of these intervals to combine with the last interval. [7, 10], for a total of 3 qualifying intervals. Thus, we print 3 on a new line.

HackerRank Interval Selection Problem Solution

Table of Contents

Interval Selection C Solution


#include <stdio.h>


int main()
{

int i, j;
	
int T, N;
	
scanf("%d", &T);

	
for (; T > 0; T--) {
		scanf("%d", &N);
		
unsigned int inter[N][2];

		
for (i = 0; i < N; i++)
			
scanf("%d %d", &(inter[i][0]), &(inter[i][1]));

	
for (i = 0; i < N; i++) {
	for (j = i+1; j < N; j++) {

if (inter[i][1] > inter[j][1] ||
(inter[i][1] == inter[j][1] && inter[i][0] > inter[j][0])) {

int temp1, temp2;
	 temp1 = inter[i][0]; temp2 = inter[i][1];
		inter[i][0] = inter[j][0]; inter[i][1] = inter[j][1];
	
inter[j][0] = temp1; inter[j][1] = temp2;
				}
	}
	}

		
int count = 0;
		
unsigned int end = 0, end2 = 0;
		
for (i = 0; i < N; i++) {
	
if (end2 < inter[i][0]) {
	count++;
	
if (end >= inter[i][0]) {
	end2 = end;
	}
		
end = inter[i][1];
	
}
 }


printf("%d\n", count);
	}
	
return 0;

}

Interval Selection C++ Solution

#include <iostream>
#include <set>

using namespace std;

class Interval{
public:
int begin;int end;
Interval(){
    begin=0;end=0;
}

Interval(int _b,int _e){
    begin=_b;end=_e;
}

 bool operator==(const Interval& i) const {
     return (begin==i.begin)&&(end==i.end);
 }

 bool operator<(const Interval& i) const {
     return begin<i.begin;
 }
};


multiset<Interval> inters;
multiset<int> iends;

multiset<Interval>::iterator it1;
multiset<int>::iterator et1;

int main(){
int n,t,a,b;
scanf("%d",&t);
while(t--){
    inters.clear();
    iends.clear();
    scanf("%d",&n);
    while(n--){
        scanf("%d%d",&a,&b);
        Interval inter(a,b);
        inters.insert(inter);
    }
    it1=inters.begin();
    while(it1!=inters.end()){
        iends.insert(it1->end);
        et1=iends.lower_bound(it1->begin);
        multiset<int>::iterator t=et1;
        if((++et1!=iends.end())&&(++et1!=iends.end())){
            while(et1!=iends.end()){
                multiset<int>::iterator te=et1;
                et1++;
                iends.erase(te);
            }
        }
        it1++;
    }
    printf("%u\n",iends.size());
}
return 0;
}

Interval Selection C Sharp Solution

using System.CodeDom.Compiler;
using System.Collections.Generic;
using System.Collections;
using System.ComponentModel;
using System.Diagnostics.CodeAnalysis;
using System.Globalization;
using System.IO;
using System.Linq;
using System.Reflection;
using System.Runtime.Serialization;
using System.Text.RegularExpressions;
using System.Text;
using System;

class Result
{

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

    public static int intervalSelection(List<List<int>> intervals)
    {
        intervals.ForEach(o => Console.WriteLine(string.Join(" ", o.ToList())));
        var arr = intervals.ToArray();
            Array.Sort(arr, (a, b) => a[1] - b[1]);
            var count = 0;
            var busy = new int[2];
            foreach (var x in arr)
            {
                if (x[0] > busy[1])
                {
                    ++count;
                    busy[1] = x[1];
                }
                else if (x[0] > busy[0])
                {
                    ++count;
                    busy[0] = busy[1];
                    busy[1] = x[1];
                }
            }

            return count;
    }

}

class Solution
{
    public static void Main(string[] args)
    {
        TextWriter textWriter = new StreamWriter(@System.Environment.GetEnvironmentVariable("OUTPUT_PATH"), true);

        int s = Convert.ToInt32(Console.ReadLine().Trim());

        for (int sItr = 0; sItr < s; sItr++)
        {
            int n = Convert.ToInt32(Console.ReadLine().Trim());

            List<List<int>> intervals = new List<List<int>>();

            for (int i = 0; i < n; i++)
            {
                intervals.Add(Console.ReadLine().TrimEnd().Split(' ').ToList().Select(intervalsTemp => Convert.ToInt32(intervalsTemp)).ToList());
            }

            int result = Result.intervalSelection(intervals);

            textWriter.WriteLine(result);
        }

        textWriter.Flush();
        textWriter.Close();
    }
}

Interval Selection Java Solution

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

class Solution{
    static int solve(int[][] intv){
        Arrays.sort(intv,(int[] a, int[] b)->a[1]-b[1]);
        int count=0, busy[][]=new int[2][2];
        for(int[] x: intv){
            if(x[0]>busy[1][1]){
                ++count;
                busy[1]=x;
            }else if(x[0]>busy[0][1]){
                ++count;
                busy[0]=x;
                if(x[1]>busy[1][1]){
                    int[] temp=busy[0];
                    busy[0]=busy[1];
                    busy[1]=temp;
                }
            }
        }
        return count;
    }
    public static void main(String[] args){
        Scanner sc=new Scanner(System.in);
        int s=sc.nextInt();
        while(s-- != 0){
            int n=sc.nextInt();
            int[][] intv=new int[n][2];
            for(int i=0;i<n;++i){
                intv[i][0]=sc.nextInt();
                intv[i][1]=sc.nextInt();
            }
            System.out.println(solve(intv));
        }
        sc.close();
    }
}

Interval Selection JavaScript Solution

'use strict';

const fs = require('fs');

process.stdin.resume();
process.stdin.setEncoding('utf-8');

let inputString = '';
let currentLine = 0;

process.stdin.on('data', function(inputStdin) {
    inputString += inputStdin;
});

process.stdin.on('end', function() {
    inputString = inputString.split('\n');

    main();
});

function readLine() {
    return inputString[currentLine++];
}

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

function intervalSelection(intervals) {
  intervals.sort((a, b) => a[1] - b[1]);
  let noOfSelections = 0;
  let busy = [[0, 0], [0, 0]];

  for (let interval of intervals) {
    if (interval[0] > busy[1][1]) {
      noOfSelections++;
      busy[1] = interval;
    } else {
      if (interval[0] > busy[0][1]) {
        noOfSelections++;
        busy[0] = interval;
        if (interval[1] > busy[1][1]) {
          [busy[0], busy[1]] = [busy[1], busy[0]];
        }
      }
    }
  }

  return noOfSelections;
}


function main() {
    const ws = fs.createWriteStream(process.env.OUTPUT_PATH);

    const s = parseInt(readLine().trim(), 10);

    for (let sItr = 0; sItr < s; sItr++) {
        const n = parseInt(readLine().trim(), 10);

        let intervals = Array(n);

        for (let i = 0; i < n; i++) {
            intervals[i] = readLine().replace(/\s+$/g, '').split(' ').map(intervalsTemp => parseInt(intervalsTemp, 10));
        }

        const result = intervalSelection(intervals);

        ws.write(result + '\n');
    }

    ws.end();
}

Interval Selection Python Solution

s = int(input().strip())
for _ in range(s):
    n = int(input().strip())
    a = []
    b = []
    for i in range(n):
        ai,bi = [int(x) for x in input().strip().split()]
        a.append(ai)
        b.append(bi)
    a,b = zip(*sorted(zip(a,b), key = lambda x:x[0]))
    a,b = list(a),list(b)
    res1,res2 = (a[0],b[0]),(a[1],b[1])
    if b[1] < b[0]:
        res1,res2 = res2,res1
    count = 2
    for i in range(2,n):
        if a[i] > res1[1]:
            count += 1
            res1 = (a[i],b[i])
        elif b[i] < res2[1]:
            res2 = (a[i],b[i])
        if res2[1] < res1[1]:
            res1,res2 = res2,res1
    print(count)