Header Ads Widget

Attendance | hackerearth solution

Rajnish Tripathi 21:14

 Problem

As per COVID-19 rules, your college is taking online classes. Your professor takes class from StartTime(hh:mm:ss) to EndTime(hh:mm:ss). He uses a chrome extension to track when a student joins the class and leaves the class with their Student ID(SID). He stores it in a student tracker file and then circulates it in your college group.  Now, your teacher is very strict. He wants to take attendance at a moment when the number of students present in the class is minimum. If there are multiple such times he can choose a time with equal probability and will take the attendance. Now, you know your teacher's algorithm and you have access to the student tracker file.

Task

Print 0 if the probability that you (SID=1) will get the attendance is zero otherwise print the probability in P/Q format where GCD(P, Q)=1, where GCD(P, Q) denotes the greatest common divisor of integers P and Q.

Note: Each student can join the class at multiple intervals. Like they can join at "12:00:00" then leave at "12:15:00", then again join at "12:35:00", and leave at "12:50:00".

Example

Assumptions

  • N = 2
  • StartTime = "12:00:00"
  • EndTime = "12:45:00"
  • The next N lines are:
    • SID1 = 2, M1 = 2, Time1 = [[12:00:00, 12:15:00] [12:20:00, 12:45:00]]
    • SID2 = 1, M2 = 1, Time2 = [[12:00:00, 12:44:00]]

Approach

  • The minimum number of students is 1 and is at any second from "12:15:00" to "12:19:59" or at any second from "12:44:00" to "12:44:59".
  • During these times you are available from "12:15:00" to "12:19:59".
  • So the probability that you(SID=1) will get the attendance is 5/6.

Input format

Note: This is the input format you must use to provide custom input (available above the Compile and Test button).

  • The first line contains N denoting the number of students.
  • The second line contains two space-separated strings StartTime and EndTime of class in hh:mm: ss format("00:00:00" to "23:59:59")
  • The next N lines have Student ID(SID), the number of intervals the student joined the class(M), and M pairs of [ArrivalTime, LeaveTime] in hh:mm:ss format for each M interval.

Output format

Print 0 if the probability that you (SID=1) will get the attendance is zero otherwise print the probability in P/Q format where GCD(P, Q)=1, where GCD(P, Q) denotes the greatest common divisor of integers P and Q.

Constraints

 2≤�≤10300:00:00≤���������<�������≤23:59:591≤����≤1031≤��≤5

Sample Input
3
12:00:00 13:00:00
2 2 12:00:00 12:25:00 12:56:00 13:00:00
1 1 12:00:00 12:56:00
3 1 12:00:00 13:00:00
Sample Output
31/35
Time Limit: 2
Memory Limit: 256
Source Limit:
Explanation

Example

Given

  • N = 3
  • StartTime = "12:00:00"
  • EndTime = "13:00:00"
  • Next N lines are:
    • SID1 = 2, M1 = 2, Time1 = [[12:00:00, 12:25:00] [12:56:00, 13:00:00]]
    • SID2 = 1, M2 = 1, Time2 = [[12:00:00, 12:56:00]]
    • SID2 = 3, M2 = 1, Time2 = [[12:00:00, 13:00:00]]

Approach

  • The minimum number of students is 2 and is at any second from "12:25:00" to "12:59:59".
  • During these times you are available from "12:25:00" to "12:55:59".
  • So the probability that you(SID=1) will get the attendance is 31/35.
Code(C++):-
#include <bits/stdc++.h>
using namespace std;
#define ll long long
int inSeconds(string &s){
int ans = ((s[0] - '0') * 10 + (s[1] - '0')) * 3600;
ans += ((s[3] - '0') * 10 + (s[4] - '0')) * 60;
ans += (s[6] - '0') * 10 + (s[7] - '0');
return ans;
}
bool isPart(int &time,vector<vector<int>> &r){
for(int i = 0;i < r.size();i++){
if(time >= r[i][0] and r[i][1] > time) return true;
}
return false;
}
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
int n;
cin>>n;
string start, end;
cin>>start>>end;
int sTime = inSeconds(start), eTime = inSeconds(end);
vector<vector<int>> ID;
vector<int> dp(100000, 0);
int id, m;
string s, e;
for(int i = 0;i < n;i++){
cin>>id>>m;
for(int k = 0;k < m;k++){
cin>>s>>e;
int s1 = inSeconds(s), e1 = inSeconds(e);
dp[s1]++;
dp[e1]--;
if(id == 1) ID.push_back({s1, e1});
}
}
int nemo = 0, deno = 0, ans = 10000, curr = 0;
for(int i = sTime;i < eTime;i++){
curr += dp[i];
if(ans > curr){
ans = curr;
deno = 1;
nemo = 0;
if(isPart(i, ID)) nemo = 1;
}
else if(ans == curr) {
deno++;
if(isPart(i, ID)) nemo++;
}
}
int g = __gcd(nemo, deno);
nemo /= g;
deno /= g;
if(nemo == 0) cout<<"0\n";
else cout<<nemo<<'/'<<deno<<'\n';
return 0;
}

Code(JAVA):-

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.*;
public class Attendance {
private static class TimeRange {
final int startTime;
final int endTime;
public TimeRange(String startTime, String endTime) {
this.startTime = getTimeInSeconds(startTime);
this.endTime = getTimeInSeconds(endTime);
}
public TimeRange(int startTime, int endTime) {
this.startTime = startTime;
this.endTime = endTime;
}
private static int getTimeInSeconds(String timeString) {
List<Integer> time = Arrays.stream(timeString.split(":"))
.map(data -> Integer.parseInt(data))
.toList();
return time.get(0)*3600 + time.get(1)*60 + time.get(2);
}
}
public static void main(String args []) throws Exception {
BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
Integer n = Integer.parseInt(bf.readLine());
List<String> classTimings = Arrays.stream(bf.readLine().split(" ")).toList();
TimeRange classTimeRange = new TimeRange(classTimings.get(0),classTimings.get(1));
Map<Integer,List<TimeRange>> attendanceData = new HashMap<>();
while (n>0) {
List<TimeRange> studentAttendanceRange = new ArrayList<>();
List<String> studentData = Arrays.stream(bf.readLine().split(" ")).toList();
Integer sId = Integer.parseInt(studentData.get(0));
Integer noOfVisits = Integer.parseInt(studentData.get(1));
for (int i=1;i<=noOfVisits;i++) {
TimeRange timeRange = new TimeRange(studentData.get(i*2), studentData.get(i*2+1));
studentAttendanceRange.add(timeRange);
}
attendanceData.put(sId,studentAttendanceRange);
n--;
}
calculateAttendanceProbabilityOfStudent(1,classTimeRange,attendanceData);
}
public static void calculateAttendanceProbabilityOfStudent(
int sId,
TimeRange classTimeRange,
Map<Integer,List<TimeRange>> attendanceData ) {
int[] eventInfo = new int[classTimeRange.endTime+1];
attendanceData.forEach((_sId,value) -> {
for (TimeRange timeRange : value) {
for (int i=timeRange.startTime;i< timeRange.endTime;i++) {
eventInfo[i]++;
}
}
});
int minStudents = attendanceData.size()+1;
for (int i=classTimeRange.startTime;i<classTimeRange.endTime;i++) {
int studentCount = eventInfo[i];
if (minStudents > studentCount) {
minStudents = studentCount;
}
}
int attendanceSeconds = 0;
for (int i=classTimeRange.startTime;i<classTimeRange.endTime;i++) {
int studentCount = eventInfo[i];
if (minStudents == studentCount) {
attendanceSeconds++;
}
}
int secondsInClass = 0;
for (TimeRange inClassRange : attendanceData.get(sId)) {
for (int i=inClassRange.startTime;i<inClassRange.endTime;i++) {
int studentCount = eventInfo[i];
if (minStudents == studentCount) {
secondsInClass++;
}
}
}
if (secondsInClass == 0) {
System.out.println(secondsInClass);
} else {
int gcd = getGCD(secondsInClass,attendanceSeconds);
System.out.println((secondsInClass/gcd)+"/"+(attendanceSeconds/gcd));
}
}
private static int getGCD(int x,int y) {
int gcd = 1;
for(int i = 1; i <= x && i <= y; i++)
{
if(x%i==0 && y%i==0)
gcd = i;
}
return gcd;
}
}


Recommended Post :-

HCL Coding Questions:-

Capgemini Coding Questions:-

Companies interview:-

Full C course:-    

Key points:-

Cracking the coding interview:-

 Array and string:-

Tree and graph:-

Hackerearth Problems:-

Hackerrank Problems:-

Data structure:-

 MCQs:-

Tags:

Post a Comment

0 Comments