HackerRank Interval Selection Problem Solution Yashwant Parihar, July 20, 2023August 1, 2024 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 FormatThe 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 describingthe respective starting (ai) and ending (bi) boundaries of an interval. Output FormatFor 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 ExplanationFor 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 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 CcppCSharpHackerrank Solutionsjavajavascriptpython