PROBLEM LINK:
Author: [Riddham]
Editorialist: [Riddham]
DIFFICULTY:
EASY
PREREQUISITES:
Greedy, Two pointer approach
PROBLEM:
To allocate room to a student such that it meets the criteria that the absolute difference between the desired room and available room doesn’t exceed k.
EXPLANATION:
Basically there are n applicants and m rooms and one applicant will take a room if the absolute difference between the room size
available and room size desired is less than equal to k. Hence it is a basic greedy question. Sorting both the desired room size
and available room size in ascending order and then using the two pointer technique will solve the problem.So select the first candidate
and check if first room matches the criteria. If yes assign the room and move to next candidate or else if it doesn’t satisfy the criteria
move to other room and repeat the process.
SOLUTIONS:
Code passing all subtasks
import java.util.Scanner;
import java.util.Arrays;
import java.io.IOException;
import java.io.InputStream;
import java.util.InputMismatchException;
import java.io.PrintWriter;
import java.io.BufferedWriter;
import java.io.OutputStream;
import java.io.OutputStreamWriter;
import java.io.Writer;
class InputReader {
private InputStream stream;
private byte[] buf = new byte[1024];
private int curChar;
private int numChars;
private SpaceCharFilter filter;
public InputReader(InputStream stream) {
this.stream = stream;
}
public int read() {
if (numChars == -1) {
throw new InputMismatchException();
}
if (curChar >= numChars) {
curChar = 0;
try {
numChars = stream.read(buf);
} catch (IOException e) {
throw new InputMismatchException();
}
if (numChars <= 0) {
return -1;
}
}
return buf[curChar++];
}
public int readInt() {
int c = read();
while (isSpaceChar(c)) {
c = read();
}
int sgn = 1;
if (c == '-') {
sgn = -1;
c = read();
}
int res = 0;
do {
if (c < '0' || c > '9') {
throw new InputMismatchException();
}
res *= 10;
res += c - '0';
c = read();
} while (!isSpaceChar(c));
return res * sgn;
}
public String readString() {
int c = read();
while (isSpaceChar(c)) {
c = read();
}
StringBuilder res = new StringBuilder();
do {
res.appendCodePoint(c);
c = read();
} while (!isSpaceChar(c));
return res.toString();
}
public double readDouble() {
int c = read();
while (isSpaceChar(c)) {
c = read();
}
int sgn = 1;
if (c == '-') {
sgn = -1;
c = read();
}
double res = 0;
while (!isSpaceChar(c) && c != '.') {
if (c == 'e' || c == 'E') {
return res * Math.pow(10, readInt());
}
if (c < '0' || c > '9') {
throw new InputMismatchException();
}
res *= 10;
res += c - '0';
c = read();
}
if (c == '.') {
c = read();
double m = 1;
while (!isSpaceChar(c)) {
if (c == 'e' || c == 'E') {
return res * Math.pow(10, readInt());
}
if (c < '0' || c > '9') {
throw new InputMismatchException();
}
m /= 10;
res += (c - '0') * m;
c = read();
}
}
return res * sgn;
}
public long readLong() {
int c = read();
while (isSpaceChar(c)) {
c = read();
}
int sgn = 1;
if (c == '-') {
sgn = -1;
c = read();
}
long res = 0;
do {
if (c < '0' || c > '9') {
throw new InputMismatchException();
}
res *= 10;
res += c - '0';
c = read();
} while (!isSpaceChar(c));
return res * sgn;
}
public boolean isSpaceChar(int c) {
if (filter != null) {
return filter.isSpaceChar(c);
}
return c == ' ' || c == '\n' || c == '\r' || c == '\t' || c == -1;
}
public String next() {
return readString();
}
public interface SpaceCharFilter {
public boolean isSpaceChar(int ch);
}
}
class OutputWriter {
private final PrintWriter writer;
public OutputWriter(OutputStream outputStream) {
writer = new PrintWriter(new BufferedWriter(new OutputStreamWriter(outputStream)));
}
public OutputWriter(Writer writer) {
this.writer = new PrintWriter(writer);
}
public void print(Object... objects) {
for (int i = 0; i < objects.length; i++) {
if (i != 0) {
writer.print(' ');
}
writer.print(objects[i]);
}
writer.flush();
}
public void printLine(Object... objects) {
print(objects);
writer.println();
writer.flush();
}
public void close() {
writer.close();
}
public void flush() {
writer.flush();
}
}
class Codechef {
public static void main(String[] args) {
InputReader inp=new InputReader(System.in);
OutputWriter out=new OutputWriter(System.out);
int n=inp.readInt();
int m=inp.readInt();
int k=inp.readInt();
int a[]=new int[n];
int b[]=new int[m];
for(int i=0;i<n;i++)
a[i]=inp.readInt();
for(int i=0;i<m;i++)
b[i]=inp.readInt();
Arrays.sort(a);
Arrays.sort(b);
int ptr1=0,ptr2=0,count=0;
while(ptr1!=n&&ptr2!=m)
{
int left=a[ptr1]-k;
int right=a[ptr1]+k;
if(b[ptr2]<left)
ptr2++;
else if(b[ptr2]>right)
ptr1++;
else
{
count++;
ptr1++;
ptr2++;
}
}
System.out.println(count);
}
}
The above code has a input output template used. Actual answer is in the class Codechef
We hope you enjoyed the problems and if you have any questions, do ask us right away on this thread.