Given a list of intervals interval[] where each interval contains two integers L and R, the task is to assign intervals to two different processors such that there are no overlapping intervals for each processor. To assign the interval[i] to the first processor, print āFā and to assign it to the second processor, print āSā.
Note: If there is no possible solution print -1.
Examples:Ā
Input: interval[] = {{360, 480}, {420, 540}, {600, 660}}Ā
Output: S, F, SĀ
Explanation:Ā
The intervals assigned to processors are āĀ
Intervals of First Processor {{420, 540}}Ā
Intervals of Second Processor {{360, 480}, {600, 660}}Ā
As there are no overlapping intervals for each processor, it will be a valid solution.Input: interval[] = {{99, 150}, {1, 100}, {100, 301}, {2, 5}, {150, 250}}Ā
Output: S, F, F, S, SĀ
Explanation:Ā
The intervals assigned to processors are āĀ
Intervals of First Processor {{1, 100}, {100, 301}}Ā
Intervals of Second Processor {{99, 150}, {2, 5}, {150, 250}}Ā
As there are no overlapping intervals for each processor, it will be a valid solution.Ā
Approach: The idea is to use Greedy algorithm to assign the intervals to the processor.Ā
If the highest end time of the processor is less than or equal to start time of an interval, then this interval can be assigned to the processor. Otherwise, check for the another processor. If any interval cannot be assigned to any processor then there is no possible solution.Ā
Below is the illustration of the steps of the approach:Ā
- As in the current problem we have to print according to the order of the intervals. So to save the order of intervals, pair the intervals with their index.
- Sort the intervals by their start time. i.e. L.
- Iterate over the intervals and assign the intervals to the processors as follows:Ā Ā
if (interval[i][0] >= firstProcessorEndTime)
answer[interval[i]] = "F"
firstProcessorEndTime =
max(firstProcessorEndTime, interval[i][0])
else if (interval[i][0] >= secondProcessorEndTime)
answer[interval[i]] = "S"
secondProcessorEndTime =
max(secondProcessorEndTime, interval[i][0])
else
print(-1)
Below is the implementation of the above approach:
C++
// C++ implementation for intervals// scheduling to two processors such// that there are no overlapping intervals#include <bits/stdc++.h>using namespace std;Ā
// Function to assign the intervals// to two different processorsvoid assignIntervals(vector<vector<int> > interval, int n){Ā
Ā Ā Ā Ā //Ā Loop to pair the intervalĀ Ā Ā Ā //Ā with their indicesĀ Ā Ā Ā for (int i = 0; i < n; i++)Ā Ā Ā Ā Ā Ā Ā Ā interval[i].push_back(i);Ā
Ā Ā Ā Ā // sorting the interval byĀ Ā Ā Ā // their start timesĀ Ā Ā Ā sort(interval.begin(), interval.end());Ā
Ā Ā Ā Ā int firstEndTime = -1;Ā Ā Ā Ā int secondEndTime = -1;Ā Ā Ā Ā char find = ' ';Ā Ā Ā Ā bool flag = false;Ā
Ā Ā Ā Ā // Loop to iterate over theĀ Ā Ā Ā // intervals with their start timeĀ Ā Ā Ā for (int i = 0; i < n; i++) {Ā Ā Ā Ā Ā Ā Ā Ā if (interval[i][0] >= firstEndTime) {Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā firstEndTime = interval[i][1];Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā interval[i].push_back('S');Ā Ā Ā Ā Ā Ā Ā Ā }Ā Ā Ā Ā Ā Ā Ā Ā else if (interval[i][0] >= secondEndTime) {Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā secondEndTime = interval[i][1];Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā interval[i].push_back('F');Ā Ā Ā Ā Ā Ā Ā Ā }Ā Ā Ā Ā Ā Ā Ā Ā else {Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā flag = true;Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā break;Ā Ā Ā Ā Ā Ā Ā Ā }Ā Ā Ā Ā }Ā
Ā Ā Ā Ā // Condition to check if thereĀ Ā Ā Ā // is a possible solutionĀ Ā Ā Ā if (flag)Ā Ā Ā Ā Ā Ā Ā Ā cout << (-1);Ā Ā Ā Ā else {Ā Ā Ā Ā Ā Ā Ā Ā vector<char> form(n, ' ');Ā
Ā Ā Ā Ā Ā Ā Ā Ā for (int i = 0; i < n; i++) {Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā int indi = interval[i][2];Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā form[indi] = interval[i][3];Ā Ā Ā Ā Ā Ā Ā Ā }Ā
Ā Ā Ā Ā Ā Ā Ā Ā // form = ''.join(form)Ā Ā Ā Ā Ā Ā Ā Ā for (int i = 0; i < form.size(); i++)Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā cout << form[i] << ",";Ā Ā Ā Ā }}Ā
// Driver Codeint main(){Ā
Ā Ā Ā Ā vector<vector<int> > intervalsĀ Ā Ā Ā Ā Ā Ā Ā = { { 360, 480 }, { 420, 540 }, { 600, 660 } };Ā
Ā Ā Ā Ā // Function CallĀ Ā Ā Ā assignIntervals(intervals, intervals.size());Ā Ā Ā Ā return 0;} |
Java
// Java program for the above approach import java.util.*;Ā
public class Main {Ā
Ā Ā Ā Ā public static void main(String[] args) {Ā Ā Ā Ā Ā Ā Ā Ā // Intervals to be scheduledĀ Ā Ā Ā Ā Ā Ā Ā int[][] intervals = {Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā { 360, 480 },Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā { 420, 540 },Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā { 600, 660 }Ā Ā Ā Ā Ā Ā Ā Ā };Ā
Ā Ā Ā Ā Ā Ā Ā Ā // Function CallĀ Ā Ā Ā Ā Ā Ā Ā assignIntervals(intervals, intervals.length);Ā Ā Ā Ā }Ā
Ā Ā Ā Ā // Function to assign the intervalsĀ Ā Ā Ā // to two different processorsĀ Ā Ā Ā public static void assignIntervals(int[][] interval, int n) {Ā
Ā Ā Ā Ā Ā Ā Ā Ā // Loop to pair the intervalĀ Ā Ā Ā Ā Ā Ā Ā // with their indicesĀ Ā Ā Ā Ā Ā Ā Ā for (int i = 0; i < n; i++) {Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā interval[i] = Arrays.copyOf(interval[i], interval[i].length + 1);Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā interval[i][interval[i].length - 1] = i;Ā Ā Ā Ā Ā Ā Ā Ā }Ā
Ā Ā Ā Ā Ā Ā Ā Ā // Sorting the interval by their start timesĀ Ā Ā Ā Ā Ā Ā Ā Arrays.sort(interval, Comparator.comparingInt(a -> a[0]));Ā
Ā Ā Ā Ā Ā Ā Ā Ā int firstEndTime = -1;Ā Ā Ā Ā Ā Ā Ā Ā int secondEndTime = -1;Ā Ā Ā Ā Ā Ā Ā Ā boolean flag = false;Ā
Ā Ā Ā Ā Ā Ā Ā Ā // Loop to iterate over theĀ Ā Ā Ā Ā Ā Ā Ā // intervals with their start timeĀ Ā Ā Ā Ā Ā Ā Ā for (int i = 0; i < n; i++) {Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā if (interval[i][0] >= firstEndTime) {Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā firstEndTime = interval[i][1];Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā interval[i] = Arrays.copyOf(interval[i], interval[i].length + 1);Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā interval[i][interval[i].length - 1] = 'S';Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā } else if (interval[i][0] >= secondEndTime) {Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā secondEndTime = interval[i][1];Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā interval[i] = Arrays.copyOf(interval[i], interval[i].length + 1);Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā interval[i][interval[i].length - 1] = 'F';Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā } else {Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā flag = true;Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā break;Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā }Ā Ā Ā Ā Ā Ā Ā Ā }Ā
Ā Ā Ā Ā Ā Ā Ā Ā // Condition to check if thereĀ Ā Ā Ā Ā Ā Ā Ā // is a possible solutionĀ Ā Ā Ā Ā Ā Ā Ā if (flag) {Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā System.out.println("-1");Ā Ā Ā Ā Ā Ā Ā Ā } else {Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā List<Character> form = new ArrayList<>(Collections.nCopies(n, ' '));Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā for (int i = 0; i < n; i++) {Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā int indi = interval[i][2];Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā form.set(indi, (char) interval[i][3]);Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā }Ā
Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā // Print the resultĀ Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā String output = form.toString();Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā System.out.println(output);Ā Ā Ā Ā Ā Ā Ā Ā }Ā Ā Ā Ā }}Ā
// This code is contributed by Prince Kumar |
Python3
# Python implementation for intervals# scheduling to two processors such # that there are no overlapping intervalsĀ
# Function to assign the intervals # to two different processorsdef assignIntervals(interval, n):Ā Ā Ā Ā Ā Ā Ā Ā Ā # Loop to pair the intervalĀ Ā Ā Ā # with their indicesĀ Ā Ā Ā for i in range(n):Ā Ā Ā Ā Ā Ā Ā Ā interval[i].append(i)Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā # sorting the interval by Ā Ā Ā Ā # their startb timesĀ Ā Ā Ā interval.sort(key = lambda x: x[0])Ā Ā Ā Ā Ā Ā Ā Ā Ā firstEndTime = -1Ā Ā Ā Ā secondEndTime = -1Ā Ā Ā Ā find = ''Ā Ā Ā Ā flag = FalseĀ Ā Ā Ā Ā Ā Ā Ā Ā # Loop to iterate over theĀ Ā Ā Ā # intervals with their start timeĀ Ā Ā Ā for i in range(n):Ā Ā Ā Ā Ā Ā Ā Ā if interval[i][0] >= firstEndTime:Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā firstEndTime = interval[i][1]Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā interval[i].append('S')Ā Ā Ā Ā Ā Ā Ā Ā elif interval[i][0] >= secondEndTime:Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā secondEndTime = interval[i][1]Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā interval[i].append('F')Ā Ā Ā Ā Ā Ā Ā Ā else:Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā flag = TrueĀ Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā breakĀ Ā Ā Ā Ā Ā Ā Ā Ā # Condition to check if thereĀ Ā Ā Ā # is a possible solutionĀ Ā Ā Ā if flag:Ā Ā Ā Ā Ā Ā Ā Ā print(-1)Ā Ā Ā Ā else:Ā Ā Ā Ā Ā Ā Ā Ā form = ['']*nĀ Ā Ā Ā Ā Ā Ā Ā for i in range(n):Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā indi = interval[i][2]Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā form[indi] = interval[i][3]Ā Ā Ā Ā Ā Ā Ā Ā # form = ''.join(form)Ā Ā Ā Ā Ā Ā Ā Ā print(form, ", ")Ā
# Driver CodeĀ Ā Ā if __name__ == "__main__":Ā Ā Ā Ā intervals = [[360, 480], [420, 540], [600, 660]]Ā Ā Ā Ā Ā Ā Ā Ā Ā # Function CallĀ Ā Ā Ā assignIntervals(intervals, len(intervals)) |
C#
using System;using System.Collections.Generic;using System.Linq;Ā
class MainClass {Ā Ā Ā Ā public static void Main(string[] args) {Ā Ā Ā Ā Ā Ā Ā Ā // intervals to be scheduledĀ Ā Ā Ā Ā Ā Ā Ā int[][] intervals = {Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā new int[] {360, 480},Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā new int[] {420, 540},Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā new int[] {600, 660}Ā Ā Ā Ā Ā Ā Ā Ā };Ā
Ā Ā Ā Ā Ā Ā Ā Ā // Function CallĀ Ā Ā Ā Ā Ā Ā Ā AssignIntervals(intervals, intervals.Length);Ā Ā Ā Ā }Ā
Ā Ā Ā Ā // Function to assign the intervalsĀ Ā Ā Ā // to two different processorsĀ Ā Ā Ā public static void AssignIntervals(int[][] interval, int n) {Ā Ā Ā Ā Ā Ā Ā Ā //Ā Loop to pair the intervalĀ Ā Ā Ā Ā Ā Ā Ā //Ā with their indicesĀ Ā Ā Ā Ā Ā Ā Ā for (int i = 0; i < n; i++) {Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā interval[i] = interval[i].Concat(new int[] {i}).ToArray();Ā Ā Ā Ā Ā Ā Ā Ā }Ā
Ā Ā Ā Ā Ā Ā Ā Ā // sorting the interval byĀ Ā Ā Ā Ā Ā Ā Ā // their start timesĀ Ā Ā Ā Ā Ā Ā Ā interval = interval.OrderBy(x => x[0]).ToArray();Ā
Ā Ā Ā Ā Ā Ā Ā Ā int firstEndTime = -1;Ā Ā Ā Ā Ā Ā Ā Ā int secondEndTime = -1;Ā Ā Ā Ā Ā Ā Ā Ā bool flag = false;Ā
Ā Ā Ā Ā Ā Ā Ā Ā // Loop to iterate over theĀ Ā Ā Ā Ā Ā Ā Ā // intervals with their start timeĀ Ā Ā Ā Ā Ā Ā Ā for (int i = 0; i < n; i++) {Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā if (interval[i][0] >= firstEndTime) {Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā firstEndTime = interval[i][1];Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā interval[i] = interval[i].Concat(new int[] {'S'}).ToArray();Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā } else if (interval[i][0] >= secondEndTime) {Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā secondEndTime = interval[i][1];Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā interval[i] = interval[i].Concat(new int[] {'F'}).ToArray();Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā } else {Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā flag = true;Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā break;Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā }Ā Ā Ā Ā Ā Ā Ā Ā }Ā
Ā Ā Ā Ā Ā Ā Ā Ā // Condition to check if thereĀ Ā Ā Ā Ā Ā Ā Ā // is a possible solutionĀ Ā Ā Ā Ā Ā Ā Ā if (flag) {Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Console.WriteLine("-1");Ā Ā Ā Ā Ā Ā Ā Ā } else {Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā List<char> form = new List<char>(new char[n]);Ā
Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā for (int i = 0; i < n; i++) {Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā int indi = interval[i][2];Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā form[indi] = (char)interval[i][3];Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā }Ā
Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā string output = string.Join( ",", form);Ā
Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Console.WriteLine("["+output+"]");Ā Ā Ā Ā Ā Ā Ā Ā }Ā Ā Ā Ā }} |
Javascript
// JavaScript implementation for intervals// scheduling to two processors such// that there are no overlapping intervalsĀ
// Function to assign the intervals// to two different processorsfunction assignIntervals(interval, n) {Ā Ā Ā Ā Ā Ā Ā Ā Ā // Loop to pair the intervalĀ Ā Ā Ā // with their indicesĀ Ā Ā Ā for (let i = 0; i < n; i++) {Ā Ā Ā Ā Ā Ā Ā Ā interval[i].push(i);Ā Ā Ā Ā }Ā Ā Ā Ā Ā Ā Ā Ā Ā // sorting the interval by Ā Ā Ā Ā // their startb timesĀ Ā Ā Ā interval.sort((a, b) => a[0] - b[0]);Ā Ā Ā Ā Ā Ā Ā Ā Ā let firstEndTime = -1;Ā Ā Ā Ā let secondEndTime = -1;Ā Ā Ā Ā let find = '';Ā Ā Ā Ā let flag = false;Ā Ā Ā Ā Ā Ā Ā Ā Ā // Loop to iterate over theĀ Ā Ā Ā // intervals with their start timeĀ Ā Ā Ā for (let i = 0; i < n; i++) {Ā Ā Ā Ā Ā Ā Ā Ā if (interval[i][0] >= firstEndTime) {Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā firstEndTime = interval[i][1];Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā interval[i].push('S');Ā Ā Ā Ā Ā Ā Ā Ā } else if (interval[i][0] >= secondEndTime) {Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā secondEndTime = interval[i][1];Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā interval[i].push('F');Ā Ā Ā Ā Ā Ā Ā Ā } else {Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā flag = true;Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā break;Ā Ā Ā Ā Ā Ā Ā Ā }Ā Ā Ā Ā }Ā Ā Ā Ā Ā Ā Ā Ā Ā // Condition to check if thereĀ Ā Ā Ā // is a possible solutionĀ Ā Ā Ā if (flag) {Ā Ā Ā Ā Ā Ā Ā Ā console.log(-1);Ā Ā Ā Ā } else {Ā Ā Ā Ā Ā Ā Ā Ā let form = Array(n).fill('');Ā Ā Ā Ā Ā Ā Ā Ā for (let i = 0; i < n; i++) {Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā let indi = interval[i][2];Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā Ā form[indi] = interval[i][3];Ā Ā Ā Ā Ā Ā Ā Ā }Ā Ā Ā Ā Ā Ā Ā Ā // form = form.join('');Ā Ā Ā Ā Ā Ā Ā Ā console.log(form, ", ");Ā Ā Ā Ā }}Ā
// Driver Codelet intervals = [[360, 480], [420, 540], [600, 660]];Ā
// Function CallassignIntervals(intervals, intervals.length);Ā
// This code is contributed by phasing17. |
Output
S,F,S,
Time Complexity: O(NlogN)
Auxiliary Space: O(N)Ā
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!
