We are given N jobs, and their starting and ending times. We can do two jobs simultaneously at a particular moment. If one job ends at the same moment some other show starts then we can’t do them. We need to check if it is possible to complete all the jobs or not.
Examples:
Input : Start and End times of Jobs
1 2
2 3
4 5
Output : Yes
By the time third job starts, both jobs
are finished. So we can schedule third
job.
Input : Start and End times of Jobs
1 5
2 4
2 6
1 7
Output : No
All 4 jobs needs to be scheduled at time
3 which is not possible.
We first sort the jobs according to their starting time. Then we start two jobs simultaneously and check if the starting time of third job and so on is greater than the ending time of and of the previous two jobs.
The implementation the above idea is given below.
C++
// CPP program to check if all jobs can be scheduled// if two jobs are allowed at a time.#include <bits/stdc++.h>using namespace std;bool checkJobs(int startin[], int endin[], int n){ // making a pair of starting and ending time of job vector<pair<int, int> > a; for (int i = 0; i < n; i++) a.push_back(make_pair(startin[i], endin[i])); // sorting according to starting time of job sort(a.begin(), a.end()); // starting first and second job simultaneously long long tv1 = a[0].second, tv2 = a[1].second; for (int i = 2; i < n; i++) { // Checking if starting time of next new job // is greater than ending time of currently // scheduled first job if (a[i].first >= tv1) { tv1 = tv2; tv2 = a[i].second; } // Checking if starting time of next new job // is greater than ending time of currently // scheduled second job else if (a[i].first >= tv2) tv2 = a[i].second; else return false; } return true;}// Driver codeint main(){ int startin[] = { 1, 2, 4 }; // starting time of jobs int endin[] = { 2, 3, 5 }; // ending times of jobs int n = sizeof(startin) / sizeof(startin[0]); cout << checkJobs(startin, endin, n); return 0;} |
Java
// Java program to check if all jobs can be scheduled// if two jobs are allowed at a time.import java.util.*;// Generic Pair class definitionclass Pair<T, U> { // Data members private T key; private U value; // Constructor public Pair(T key, U value) { this.key = key; this.value = value; } // Getters public T getKey() { return key; } public U getValue() { return value; }}class GFG { public static boolean checkJobs(int[] startin, int[] endin, int n) { // making a pair of starting and ending time of job List<Pair<Integer, Integer> > a = new ArrayList<>(); for (int i = 0; i < n; i++) a.add(new Pair<Integer, Integer>(startin[i], endin[i])); // sorting according to starting time of job Collections.sort( a, new Comparator<Pair<Integer, Integer> >() { public int compare(Pair<Integer, Integer> a, Pair<Integer, Integer> b) { return a.getKey().compareTo(b.getKey()); } }); // starting key and value job simultaneously long tv1 = a.get(0).getValue(), tv2 = a.get(1).getValue(); for (int i = 2; i < n; i++) { // Checking if starting time of next new job // is greater than ending time of currently // scheduled key job if (a.get(i).getKey() >= tv1) { tv1 = tv2; tv2 = a.get(i).getValue(); } // Checking if starting time of next new job // is greater than ending time of currently // scheduled value job else if (a.get(i).getKey() >= tv2) tv2 = a.get(i).getValue(); else return false; } return true; } // Driver code public static void main(String[] args) { int[] startin = { 1, 2, 4 }; // starting time of jobs int[] endin = { 2, 3, 5 }; // ending times of jobs int n = startin.length; System.out.println(checkJobs(startin, endin, n)); }} |
Python3
# Python3 program to check if all # jobs can be scheduled if two jobs # are allowed at a time. def checkJobs(startin, endin, n): # making a pair of starting and # ending time of job a = [] for i in range(0, n): a.append([startin[i], endin[i]]) # sorting according to starting # time of job a.sort() # starting first and second job # simultaneously tv1 = a[0][1] tv2 = a[1][1] for i in range(2, n): # Checking if starting time of next # new job is greater than ending time # of currently scheduled first job if (a[i][0] >= tv1) : tv1 = tv2 tv2 = a[i][1] # Checking if starting time of next # new job is greater than ending time # of currently scheduled second job elif (a[i][0] >= tv2) : tv2 = a[i][1] else: return 0 return 1# Driver Code if __name__ == '__main__': startin = [1, 2, 4] # starting time of jobs endin = [2, 3, 5] # ending times of jobs n = 3 print(checkJobs(startin, endin, n))# This code is contributed by# Shubham Singh(SHUBHAMSINGH10) |
C#
using System;class Program{ static bool CheckJobs(int[] startin, int[] endin, int n) { // making a pair of starting and ending time of job (int, int)[] a = new (int, int)[n]; for (int i = 0; i < n; i++) a[i] = (startin[i], endin[i]); // sorting according to starting time of job Array.Sort(a); // starting first and second job simultaneously long tv1 = a[0].Item2, tv2 = a[1].Item2; for (int i = 2; i < n; i++) { // Checking if starting time of next new job // is greater than ending time of currently // scheduled first job if (a[i].Item1 >= tv1) { tv1 = tv2; tv2 = a[i].Item2; } // Checking if starting time of next new job // is greater than ending time of currently // scheduled second job else if (a[i].Item1 >= tv2) { tv2 = a[i].Item2; } else { return false; } } return true; } static void Main() { int[] startin = { 1, 2, 4 }; // starting time of jobs int[] endin = { 2, 3, 5 }; // ending times of jobs int n = startin.Length; Console.WriteLine(CheckJobs(startin, endin, n)); }} |
Javascript
// JS codefunction checkJobs(startin, endin, n) { let a = []; for (let i = 0; i < n; i++) { a.push([startin[i], endin[i]]); } a.sort((a, b) => a[0] - b[0]); let tv1 = a[0][1], tv2 = a[1][1]; for (let i = 2; i < n; i++) { if (a[i][0] >= tv1) { tv1 = tv2; tv2 = a[i][1]; } else if (a[i][0] >= tv2) { tv2 = a[i][1]; } else { return false; } } return true;}let startin = [1, 2, 4];let endin = [2, 3, 5];let n = startin.length;console.log(checkJobs(startin, endin, n)); |
Output
1
Time Complexity: O(n log n), where n is the number of jobs. The sorting operation on the job array takes O(n log n) time, and the for loop iterates over the array once, which takes O(n) time. Hence, the overall time complexity is O(n log n).
Auxiliary Space: O(1). The algorithm uses constant extra space for storing temporary variables.
An alternate solution is to find maximum number of jobs that needs to be scheduled at any time. If this count is more than 2, return false. Else return true.
This article is contributed by Sarthak Kohli. If you like neveropen and would like to contribute, you can also write an article using write.geeksforgeeks.org or mail your article to review-team@geeksforgeeks.org. See your article appearing on the neveropen main page and help other Geeks.
Please write comments if you find anything incorrect, or you want to share more information about the topic discussed above.
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
