HackerRank Interval Selection Problem Solution

Yashwant Parihar,

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:

  1. 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

4
3
1 2
2 3
2 4
3
1 5
1 5
1 5
4
1 10
1 3
4 6
7 10
4
1 10
1 3
3 6
7 10

Sample Output

2
2
4
3

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
HackerRank Interval Selection Problem Solution

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)
c C# C++ HackerRank Solutions java javascript python