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