'가장 많은 아이스크림을 넣을 수 있는 냉장고 찾기' 방법의 반례입니다.

붉은 선) 가운데 네 개의 아이스크림을 넣을 수 있는 온도에 맞춰 세팅하게 되면 왼쪽과 오른쪽에 각각 하나씩이 남으므로 냉장고를 3개 써야 합니다.

파란 선) 사실은 두 개의 냉장고로 모든 아이스크림을 커버할 수 있습니다.

코드에서 사용한 방법은 다음과 같습니다.

1. 범위를 정렬합니다. 범위의 하한값이 작을수록 앞에 오고, 하한이 같다면 상한이 높은, 다시말해 범위가 넓은 것이 앞에 옵니다.

2. 가장 앞에 오는 것부터 차례대로 냉장고에 집어넣습니다.

3. 더 이상 냉장고에 넣을 수 없으면 새 냉장고를 준비합니다.

4. 아이스크림이 남아 있다면 2로 돌아갑니다.

이 방법을 사용하면 최적해를 구할 수 있습니다. 전체 아이스크림 집합을 U라고 하면, (2~3)의 과정에서 냉장고에 넣기 위해 선택된 아이스크림들은 L이라고 합시다. L인 이유는 이 아이스크림의 온도 범위들을 수직선 위에 올려 놓았을 때에 하한값 기준으로 가장 왼쪽에 존재하고 있을 것이라 Left에서 따서 붙인 이름입니다.

F(A) = 아이스크림 집합 A를 모두 커버할 수 있는 최소 냉장고의 수 라고 정의합시다.

위 방법이 최적해를 구한다는 것을 보이기 위해서는 F(U) = F(U-L) + 1 이라는 것을 보이면 됩니다. L은 냉장고 하나에 모두 넣을 수 있으니까요.

냉장고가 L을 모두 커버할 수 있는 온도의 범위는 [ max(lower bounds of L), min(upper bounds of L) ] 이 되겠지요? 이 범위를 R이라고 합시다.

그런데 위에서 말한 것처럼 정렬해서 차례대로 냉장고에 넣을 경우에

U-L에 있는 아이스크림들은 무조건 하한값이 R의 하한값보다 큽니다. U가 정렬되어 있기 때문에 작은 건 말이 안 되고, 같은 것도 있을 수 없습니다.

다시 말해서 U-L의 온도 범위를 커버하는 그 어떤 냉장고로도 L을 덮지 못합니다. L을 덮기 위해서는 냉장고 하나를 추가로 써야만 하는 것이죠.

#include<vector>
#include<utility>
#include<iostream>
#include<algorithm>
#include<numeric>

using namespace std;

typedef pair<int, int> icecream_t;


// return the overlapping range of two range
pair<int, int> overlap(pair<int, int> one, pair<int, int> another){
    return make_pair(
            max(one.first, another.first),
            min(one.second, another.second)
        );
}

size_t getNumberOfFridges(vector<icecream_t> &products){
    if (products.empty()) return 0;

    size_t numFridge = 0;   
    // Sort by lower bound of temperature. 
    // If two have same lb, the longer will be forward.
    sort(products.begin(), products.end(), 
        [](icecream_t lhs, icecream_t rhs) {
            if (lhs.first == rhs.first) return lhs.second > rhs.second;     
            else return lhs.first < rhs.first;
        }
    );  

    pair<int, int> rng(INT_MIN, INT_MAX);
    for (auto p : products){
        rng = overlap(rng, p);
        if (rng.first > rng.second){
            numFridge++;
            rng = p;
        }
    }
    return numFridge + 1;
}

int main(){
    vector<icecream_t> icecreams = { { -20, -15 }, { -14, -5 }, { -18, -13 }, { -5, -3 } };

    std::cout << getNumberOfFridges(icecreams) << endl;
    return 0;
}

반례를 보고 다시 풀어봤습니다. interval tree를 보고 생각한 방법입니다. 제가 초보라서 interval tree 자료 구조는 구현하지 못했습니다.

1. 전체 온도에 대한 수평선이 있다고 가정하고 아이스크림이 유지 되는 온도의 경계점들을 기준으로 잘게 자릅니다. (자른 구간들은 양 끝 점이 포함되지 않는 열린 구간이며, 경계점들도 각각의 구간으로 생각합니다.)

2. 각각의 구간에서 어떤 아이스크림이 유지되는지 계산합니다.

3. Combination(조합)을 이용해서 가장 작은 개수로 모든 아이스크림을 유지시키는 구간을 찾아냅니다.

combination 때문에 아이스크림 개수에 따라 계산이 기하급수 적으로 늘어납니다...

icecream=function(temper){
  mat=temper
  sapply(1:nrow(mat), function(y) if(mat[y,1]>mat[y,2]) mat[y,]<<-rev(mat[y,]))

  borders=sort(unique(as.vector(mat)))
  names(borders)=borders
  intervals=apply(cbind(borders[-length(borders)], borders[-1]), 1, mean)
  names(intervals)=paste0("(", borders[-length(borders)], ",", borders[-1], ")")

  list.intersect=list()
  k=1
  for(val in c(intervals, borders)){
    name=names(c(intervals, borders))[k]
    list.intersect[[name]]=which(apply(mat, 1, function(x) (x[1]<=val && val<=x[2])))
    k=k+1
  }

  list.answer=list()
  #i=1
  for(k in 1:nrow(mat)){
    factors=combn(names(list.intersect), k)
    for(j in 1:ncol(factors)){
      t=sapply(factors[,j], function(f) list.intersect[[f]])
      if(is.list(t)) {t=unlist(t)} else {t=as.vector(t)}
      t=unique(t)
      if(identical(sort(t), 1:nrow(mat))) {
        return(k)
        #list.answer[[i]]=factors[,j]
        #i=i+1
      }
    }
    #if(length(list.answer)>0) break
  }
  #list.answer
}

이러면 반례에 대해 올바른 답을 찾아냅니다.

> icecream(matrix(c(-10, 0, 
+                   -10, 0, 
+                   -1, 0, 
+                   -15, -2, 
+                   -15, -2, 
+                   -15, -14), ncol=2, byrow=T))
[1] 2

C++로 작성했습니다.

//
//  main.cpp
//  CodingDoJang-456-CCP
//
//  Created by Chrome-MBPR on 7/9/14.
//  Copyright (c) 2014 cr2025x1. All rights reserved.
//

#include <iostream>
#include <algorithm>
#include <list>

using namespace std;

class thermal_band;



class thermal_band {
protected:
    double _upper_bound;
    double _lower_bound;
public: 
    double &upper_bound;
    double &lower_bound;

    thermal_band(double lower_bound, double upper_bound) : upper_bound(_upper_bound), lower_bound(_lower_bound) {
        this->_upper_bound = upper_bound;
        this->_lower_bound = lower_bound;
    }
};


class thermal_band_list : public list<thermal_band*> {
public:
    virtual ~thermal_band_list() {
        for_each(this->begin(), this->end(), [](thermal_band *band){delete band; });
    }
};

int main(int argc, const char * argv[])
{
    const unsigned int icecream_quantity = 4;
    double dataArray[icecream_quantity][2] = { { -20, -15 }, { -14, -5 }, { -18, -13 }, { -5, -3 } };

    thermal_band_list* TB_list = new thermal_band_list;

    for (unsigned int i = 0; i < icecream_quantity; i++) {
        if (TB_list->empty()) {
            // 리스트가 비었음. 따라서 새 원소를 만들어 추가함.
            thermal_band* newBand = new thermal_band(dataArray[i][0], dataArray[i][1]);
            TB_list->push_back(newBand);
        }
        else {
            // 리스트에 비교할 원소들이 있음.
            bool notAdded = true;           
            for (thermal_band_list::iterator itr = TB_list->begin(); itr != TB_list->end(); itr++) {
                thermal_band* itr_band = *itr;
                if (itr_band->lower_bound > dataArray[i][1]) {
                    // 현재 원소의 온도 범위가 비교 대상 아이스크림의 보관 온도 범위보다 높은 영역이다. (아이스크림 보관 온도 최대값 < 현재 원소 온도 범위 최소값)
                    // 이 원소의 바로 앞에 새 원소를 작성해, 거기에 이 아이스크림의 온도 대역을 추가한다.
                    thermal_band* newBand = new thermal_band(dataArray[i][0], dataArray[i][1]);
                    TB_list->insert(itr, newBand);
                    notAdded = false;
                    break;
                }
                // 현재 원소의 온도 범위가 비교 대상 아이스크림의 보관 온도 범위보다 낮은 영역이다. (아이스크림 보관 온도 최저값 > 현재 원소 온도 범위 최대값)
                // 다음 원소를 찾아서 진행한다.
                else if (itr_band->upper_bound < dataArray[i][0]) continue;
                else {
                    // 위의 두 조건을 만족하지 않는다면, 이 원소의 온도 범위와 비교 대상 아이스크림의 보관 온도 범위가 겹치는 부분이 있음을 뜻한다.
                    // 이 원소의 온도 범위를 아이스크림의 보관 온도 범위와 겹치는 영역만으로 축소한다.
                    if (itr_band->upper_bound > dataArray[i][1]) itr_band->upper_bound = dataArray[i][1];
                    if (itr_band->lower_bound < dataArray[i][0]) itr_band->lower_bound = dataArray[i][0];
                    notAdded = false;
                    break;
                }
            }

            // 만일 지금까지 현재 아이스크림이 처리되지 않았다면 비교 중인 아이스크림의 보관 온도 범위는 이 때까지 있는 모든 원소의 온도 범위보다 높은 영역임을 뜻한다.
            // 리스트의 가장 뒤에 이 아이스크림의 보관 범위를 가지는 원소를 추가한다.
            if (notAdded) {
                thermal_band* newBand = new thermal_band(dataArray[i][0], dataArray[i][1]);
                TB_list->push_back(newBand);
            }
        }
    }

    for_each(TB_list->begin(), TB_list->end(), [](thermal_band* band){cout << "(" << band->lower_bound << ", " << band->upper_bound << ")" << endl; });
    cout << "Total needed refrigerator = " << TB_list->size() << endl;

    delete TB_list;
    return 0;
}

1. 가장 많은 아이스크림을 보관할 수 있는 냉장고(특정온도를 가진)를 찾습니다.
2. 냉장고에 보관할 수 있는 아이스크림들을 모두 넣습니다.
3. 1, 2번을 아이스크림이 남아 있을 동안 계속 반복합니다.

가장 많은 아이스크림을 보관할 수 있는 냉장고를 찾는 이 방법에 예외 케이스가 있을것도 같은데.. 판단이 잘 안되네요...

파이썬 2.7

import operator

class IceCream:
    def __init__(self, low, high):
        self.low = low
        self.high = high

    def ok(self, c):
        return self.low <= c <= self.high

    def __repr__(self):
        return "low:%s, high:%s" % (self.low, self.high)


class Frige:
    def __init__(self, c, ice_creams):
        self.c = c
        self.ice_creams = ice_creams


def get_frige(ice_creams):
    m = {}
    for ice_cream in ice_creams:
        for c in range(ice_cream.low, ice_cream.high+1):
            if c in m:
                m[c] += 1
            else:
                m[c] = 1

    max_c = max(m.iteritems(), key=operator.itemgetter(1))[0]
    container = set()
    for ice_cream in ice_creams:
        if ice_cream.ok(max_c):
            container.add(ice_cream)

    return Frige(max_c, container)


def get_friges(ice_creams):
    friges = []
    while ice_creams:
        frige = get_frige(ice_creams)
        friges.append(frige)
        ice_creams = ice_creams - frige.ice_creams
    return friges


if __name__ == "__main__":
    ice_creams = set([
        IceCream(-20, -15),
        IceCream(-14, -5),
        IceCream(-18, -13),
        IceCream(-5, -3),
    ])
    for fr in get_friges(ice_creams):
        print fr.c, fr.ice_creams

kim jaeju 님의 반례와 알고리즘을 참고하여 다시 풀어보았습니다. (위 풀이는 반례에 의해 잘못된 것임이 증명됨)

from functools import cmp_to_key

class IceCream:
    def __init__(self, low, high):
        self.low = low
        self.high = high
        self.width = high - low


def get_frige_count(ice_creams):
    #
    # sort by low first
    # if low same: sort by width
    #
    ice_creams = sorted(ice_creams, key=cmp_to_key(
        lambda a,b: a.low-b.low if a.low-b.low!=0 else b.width-a.width))
    count = 0
    f_range = [0, 0]
    for ice_cream in ice_creams:
        if f_range[0] <= ice_cream.low <= f_range[1] \
            or f_range[0] <= ice_cream.high <= f_range[1]:
            #
            # don't need new frige
            #
            f_range = [max(f_range[0], ice_cream.low), min(f_range[1], ice_cream.high)]
        else:
            #
            # need new frige
            #
            f_range = [ice_cream.low, ice_cream.high]
            count += 1
    return count


print get_frige_count([
    IceCream(-20, -18),
    IceCream(-20, -5),
    IceCream(-15, -2),
    IceCream(-19, -4),
    IceCream(-4, -1),
    IceCream(-10, -3),
])

clojure

(defn icecream-problem
  [icecreams]

  (let [sorted-icecreams (sort-by :hi icecreams)]

    (loop [stand-icecream   (first sorted-icecreams)
           [icecream & rst] (rest sorted-icecreams)
           acc              {(:hi stand-icecream) [stand-icecream]}]

      (if-not icecream
        acc
        (if (>= (:hi stand-icecream) (:lo icecream))
          (recur stand-icecream
                 rst
                 (update-in acc [(:hi stand-icecream)] conj icecream))
          (recur icecream
                 rst
                 (assoc-in acc [(:hi icecream)] [icecream])))))))


(icecream-problem
 [{:lo -20 :hi -15}
  {:lo -14 :hi -5}
  {:lo -18 :hi -13}
  {:lo -5  :hi -3}])
;=> {-5 [{:lo -14, :hi -5} {:lo -5, :hi -3}], -15 [{:lo -20, :hi -15} {:lo -18, :hi -13}]}


(count {-5 [{:lo -14, :hi -5} {:lo -5, :hi -3}], -15 [{:lo -20, :hi -15} {:lo -18, :hi -13}]})
;=> 2

import java.util.*;

class IcecreamFactory {
    static TreeSet<Icecream> ts_icecream = new TreeSet<Icecream>();
    public static void main(String[] args) {

        ts_icecream.add(new Icecream("g", -20, -15));
        ts_icecream.add(new Icecream("f", -20, -18));
        ts_icecream.add(new Icecream("e", -20, -19));
        ts_icecream.add(new Icecream("d", -19, -15));
        ts_icecream.add(new Icecream("c", -19, -16));
        ts_icecream.add(new Icecream("b", -19, -17));
        ts_icecream.add(new Icecream("a", -16, -15));

        ArrayList<Icecream> al_icecream = new ArrayList<Icecream>(ts_icecream);

        int numberOfRefrigerator = 1;
        for (int i = 0; i < ts_icecream.size()-1; i++) {
            if(al_icecream.get(i).maxTemperature<al_icecream.get(i+1).minTemperature) numberOfRefrigerator++;
        }
        System.out.println(ts_icecream);
        System.out.println(numberOfRefrigerator);
    }
}
class Icecream implements Comparable<Icecream>{
    String name = "";
    int minTemperature;
    int maxTemperature;

    Icecream(String name, int minTemperature, int maxTemperature) {
        this.name = name;
        this.minTemperature = minTemperature;
        this.maxTemperature = maxTemperature;
    }

    public String toString() {
        return name;
    }

    //minTemperature를 먼저 비교하여 minTemperature낮은 것을 빠른순서로. minTemperature가 동일하면 maxTemperature가 높은것이 빠른 순서로.
    public int compareTo(Icecream ice) {
        if(ice.minTemperature>this.minTemperature) return -1;
        else if(ice.minTemperature<this.minTemperature) return 1;
        else{
            if(ice.maxTemperature>this.maxTemperature) return 1;
            else if(ice.maxTemperature<this.maxTemperature) return -1;
            else return 0;
        }
    }
}

맞는지는 잘 모르겠네요.

아이스크림, 냉장고, 냉장고계산기가 있습니다. 아이스크림은 적정온도 정보가 들어갑니다. 냉장고는 아이스크림 목록이 들어갑니다. 냉장고 계산기는 필요한 냉장고 갯수를 계산합니다. 전체 아이스크림 목록이 있고 이 목록에 아이스크림 정보를 넣고 냉장고 계산기에 넣어 계산합니다.

전체 아이스크림 목록 맨 처음 아이스크림부터 같은 들어갈 수 있는 종류를 찾아내어 냉장고에 넣습니다. 그리고 그 아이스크림들을 전체 아이스크림 목록에서 제거합니다. 다시 검색하고 냉장고에 넣고 전체 목록에서 삭제합니다.

#아이스크림 객체입니다.
#기본 생성은 보관 가능 온도로 생성됩니다.(예. IceCream(-10,-5))
class IceCream:

    start_temperature = 0   #보관가능 온도1
    end_temperature = 0     #보관가능 온도2
    def __init__(self, icecream_name, start_temperature, end_temperature):  
        self.icecream_name = icecream_name
        if start_temperature > end_temperature: #첫번째 인수가 뒤 인수보다 클 경우 내부 설정에서 바꿉니다(항상 start가 작은 값이 될 수 있도록.)
            self.start_temperature = end_temperature
            self.end_temperature = start_temperature
        else:
            self.start_temperature = start_temperature
            self.end_temperature = end_temperature

#냉장고 객체입니다.
class Refrigerator:

    icecream_list = []#냉장고에 들어간 아이스크림 종류 갯수 입니다.
    def add_icecream(self, icecream):#냉장고에 들어갈 수 있는 아이스크림 종류 추가
        self.icecream_list.append(icecream)
    def icecream_count(self):#현재 들어가 있는 아이스크림 종류 갯수
        return len(self.icecream_list)

#냉장고 갯수 계산기
class RefrigeratorCalculator:
    all_icecream = []#계산할 전체 아이스크림 종류 갯수
    refrigerator_list = []#필요한 냉장고 리스트
    def refrigerator_count(self):
        return len(self.refrigerator_list)
    def add_icecream(self, icecream):#아이스크림 종류 등록
        print("add_icecream %d ~ %d" % (icecream.start_temperature, icecream.end_temperature))
        self.all_icecream.append(icecream)
    #같은 냉장고에 들어갈 수 있는 아이스크림 종류 리스트
    # param1:검색할 아이스크림 리스트, param2:아이스크림
    def same_type_icecream(self, icecream_list, icecream):
        same_list = []

        for ic in icecream_list:
            print("st1=%d ic.et=%d and et1=%d ic.st=%d" % (icecream.start_temperature, ic.end_temperature, icecream.end_temperature, ic.start_temperature))
            if icecream.start_temperature <= ic.end_temperature and icecream.end_temperature >= ic.start_temperature:
                print("same")
                same_list.append(ic);
            else:
                print("not same")

        return same_list

    def calculate(self):#냉장고 갯수 계산하기

        if len(self.all_icecream) == 0:
            return 0

        while len(self.all_icecream) > 0:
            print("while all_icecream = %d" % len(self.all_icecream))
            #첫번째 아이스크림
            ic_check = self.all_icecream.pop(0)#일단 아이스크림 목록에서 삭제
            #냉장고 하나 추가
            refrigerator1 = Refrigerator()

            #냉장고 목록에 추가
            self.refrigerator_list.append(refrigerator1)

            #같이 넣을 수 있는 아이스크림 종류 목록
            same_list = self.same_type_icecream(self.all_icecream, ic_check)

            #냉장고에 넣음
            for ic in same_list:
                refrigerator1.add_icecream(ic)
                #아이스크림 목록에서는 삭제
                index = 0
                for i in range(0, len(self.all_icecream)):
                    if self.all_icecream[index] == ic:
                        del self.all_icecream[index]
                    else:
                        index = index + 1

        return len(self.refrigerator_list)



#냉장고 계산기 객체 생성
refrigeratorCal = RefrigeratorCalculator()

#아이스크림 목록
ic1 = IceCream("돼지바", -10, -5)
ic2 = IceCream("설레임", -4, 0)
ic3 = IceCream("핫바", -11, -11)

refrigeratorCal.add_icecream(ic1)
refrigeratorCal.add_icecream(ic2)
refrigeratorCal.add_icecream(ic3)

#계산
print("refrigerator count = %d" % refrigeratorCal.calculate())

정렬은 최저/ 최상 하나만 기준삼아도 될거 같아서요

from operator import itemgetter

def getNumberOfFridges(list):
    fridge = []

    list.sort(key=itemgetter(1))
    fridge.append(list[0][1])

    for item in list:
        lastFridge = fridge[len(fridge)-1]
        if not( item[0] <= lastFridge and item[1] >= lastFridge):
            fridge.append(item[1])

    print(fridge)

getNumberOfFridges([[-20, -15],[-14, -5],[-18, -13],[-5, -3]])

C#으로 작성했습니다. 약간 복잡하게 coding 한 듯 싶습니다. 1. input을 IceCreams class에 넣습니다. 2. bubblesort를 이용해서 최고온도 - 최저온도가 적은 값대로 sort 했습니다. 4. Refrigerator 함수는 재귀함수로, sort가 된 list에서 최고온도에서 최저온도로 온도를 비교해가면서 맞물리는 아이스크림의 갯수를 비교, 남은 아이스크림을 서로 비교해가며 필요한 냉장고 수를 계산했습니다.

using System;
using System.Collections.Generic;
using System.Linq;

        public class IceCream
        {
            public int TempDiff { get; set; }
            public int TempMax { get; set; }
            public int TempMin { get; set; }
            public IceCream(string tempMax, string tempMin)
            {
                TempMax = int.Parse(tempMax);
                TempMin = int.Parse(tempMin);
                TempDiff = Math.Abs(TempMax - TempMin);
            }
        }

        public int CountRefrigerators(List<IceCream> inputs, int curr, int total = 0)
        {
            var max = 0;
            var remainders = new List<IceCream>();
            while (curr >= inputs.First().TempMin)
            {
                var count = 0;
                var temp = new List<IceCream>();
                foreach (var input in inputs)
                {
                    if (input.TempMin <= curr && input.TempMax >= curr) count++;
                    else temp.Add(input);
                }
                if (max < count)
                {
                    max = count;
                    remainders = new List<IceCream>();
                    remainders.AddRange(temp);
                }
                curr--;
            }
            if (max != 0) total++;
            if (remainders.Count != 0) 
                total = CountRefrigerators(remainders, remainders.First().TempMax, total);
            return total;
        }

Kim Jaeju 님 풀이를 보고 해답을 얻었네요. 그런데 이미 최저 유지온도 순으로 정렬을 한 상태에서 냉장고 온도의 적용 가능 범위를 비교하는 것이므로, 굳이 적용 가능 범위를 계산할 필요 없이 냉장고에 적용 가능한 최고 온도와 다음에 넣을 아이스크림의 최저 유지온도만 비교하면 될 것 같습니다.

python입니다.

def getNeedRefrigerCnt(icecreams):
    refMax = -9999
    refCnt = 0

    for i in sorted(icecreams, cmp=lambda a,b:a[1]-b[1] if a[0] == b[0] else a[0] - b[0]):
        if i[0] > refMax:
            refMax = i[1]
            refCnt += 1

    return refCnt

print getNeedRefrigerCnt([(-20,-15), (-14,-5), (-18, -13), (-5, -3)])

def minRefCnt(proList):
    refCnt=0
    while len(proList)>0:
        tLine=min([t[1] for t in proList])
        refCnt += 1
        proList=[t for t in proList if t[0]>tLine]

    return refCnt

print(minRefCnt([[-5, -3], [-18, -13], [-14, -5], [-20, -15]]))

import java.util.ArrayList;
import java.util.List;

public class IceCreamFactory {

    List<int[]> rtList = null;

    public static void main(String[] args) {

        IceCreamFactory icf = new IceCreamFactory();

        System.out.println(icf.getCount(-20,-15));
        System.out.println(icf.getCount(-14,-5));
        System.out.println(icf.getCount(-18,-13));
        System.out.println(icf.getCount(-5,-3));
        System.out.println(icf.getCount(-2,-1));
        System.out.println(icf.getCount(-7,-2));

    }


    public int getCount(int min, int max) {
        if (rtList == null) {
            rtList = new ArrayList<int[]>();
            int[] m = {min, max};
            rtList.add(m);
        }

        int r = 0;

        for(int[] rm : rtList) {
            int n = rm[0];
            int x = rm[1];

            if ((n >= min && n <= max) || (x >=min && x <= max)) {
                r--;
            } else {
                r++;
            }
        }

        if (r > 0) {
            int[] m = {min, max};
            rtList.add(m);
        }


        return rtList.size();
    }

}

파이썬으로 작성했습니다. 초보인지라..^^;; 주로 리스트 데이터 형태로 처리해 보았습니다.

icecream=[[-15,-20],[-5,-14],[-13,-18],[-3,-5]]

icecream_sorted=[icecream[0]]   #아이스크림의 온도 범위의 높은 온도 순서로 재배열 합니다. 
for x in icecream[1:]:
    for i in icecream_sorted:
        if x[0]>i[0]:
            num=icecream_sorted.index(i)
            icecream_sorted.insert(num,x)
            break

fri_temp_max=icecream_sorted[0][0]  #냉장고 초기 설정값입니다.
fri_temp_min=icecream_sorted[0][1]
ftmax_list=[]
ftmin_list=[]
fri_count=0

for x in icecream_sorted[1:]:   #냉장고에 아이스크림을 추가과정(냉장고 온도 범위와 새로운 냉장고의 필요성을 결정)
    if x[0] >= fri_temp_min:
        fri_temp_max = x[0]
        if x[1] >= fri_temp_min:
            fri_temp_min = x[1]
    elif x[0] < fri_temp_min:
        ftmax_list.append(fri_temp_max)
        ftmin_list.append(fri_temp_min)
        fri_temp_max = x[0]
        fri_temp_min = x[1]
        fri_count=fri_count+1       

ftmax_list.append(fri_temp_max)
ftmin_list.append(fri_temp_min)
fri_count=fri_count+1
fri_temp=list(zip(ftmax_list,ftmin_list))

print("필요한 냉장고의 숫자는 %d개 입니다."%fri_count)    #결과 출력파트 입니다.
for x in range (0,fri_count):
    if fri_temp[x][0]==fri_temp[x][1]:
        print("%d번 냉장고 : %d도"%(x+1,fri_temp[x][0]))
    else:
        print("%d번 냉장고 : %d도에서 %d도 사이"%(x+1,fri_temp[x][0],fri_temp[x][1]))

김재주님 알고리즘 이용했습니다.

ice = [ (-20, -15),
        (-14, -5),
        (-18, -13),
        (-5, -3)]
iceMax = ice[0][1]
ref=1
ice.sort(key=lambda (a,b):(a,-b))
for (a,b) in ice:
    if iceMax < a:
        iceMax = b
        ref +=1
print ref

Ruby

누적 냉장고들(a)에 온도범위(t)가 겹치면 해당 냉장고(box)를 온도와의 교집합으로 대체, 겹치는게 없으면 냉장고 생성/입력(온도범위 t를 a에 입력). 유효온도 값을 갖는 냉장고들을 2차원 배열로 획득.

min_box = ->tpts { tpts.sort.reduce([]) {|a,t| (a.flatten&t).empty?? a<<t :
                                  a.map {|box| (box&t).empty?? box : box&e }} }

Test

case1 = [[*-20..-15],[*-14..-5],[*-18..-13],[*-5..-3]]
case2 = [[*-10..0], [*-10..0],[*-1..0],[*-15..-2],[*-15..-2],[*-15..-14]]
case3 = [[*-20..-18],[*-20..-5],[*-15..-2],[*-19..-4],[*-4..-1],[*-10..-3]]
case4 = [[*-20..-15],[*-14..-5],[*-18..-13],[*-5..-3],[-2,-1],[*-7..-2]]
case5 = [[*-10..-5],[*-4..0],[*-11..-11]]

expect(min_box[case1]).to eq [[-18, -17, -16, -15], [-5]]
expect(min_box[case2]).to eq [[-15, -14], [-1, 0]]
expect(min_box[case3]).to eq [[-19, -18], [-4, -3]]
expect(min_box[case4]).to eq [[-18, -17, -16, -15],[-5], [-2, -1]]
expect(min_box[case5]).to eq [[-11], [-10, -9, -8, -7, -6, -5], [-4, -3, -2, -1, 0]]

Output

#=> data = [[*-20..-15],[*-14..-5],[*-18..-13],[*-5..-3]]
#=> p min_box[data], min_box[data].size
[[-18, -17, -16, -15], [-5]]
2

Kim Jaeju 님 아이디어와 동일한 아이디어에서 출발했습니다.

class IceCream:
    def __init__(self, name, a, b):
        self.name = name
        self.min_temp = a
        self.max_temp = b

class Refrig:
    def __init__(self, i):
        assert isinstance(i, IceCream)
        self.list = [i]
        self.min_temp = i.min_temp
        self.max_temp = i.max_temp

    def store(self, i):
        if self.min_temp >= i.min_temp or self.max_temp <= i.max_temp:
            self.list.append(i)
            self.min_temp = max(self.min_temp, i.min_temp)
            self.max_temp = min(self.max_temp, i.max_temp)
            return True
        return False

def do(sample):
    x, *xs = sorted([IceCream(n, *v) for n, v in data.items()], key=lambda x: x.min_temp)
    r = Refrig(x)
    result = [r]
    while len(xs) > 0:
        x = xs.pop(0)
        if not r.store(x):
            r = Refrig(x)
            result.append(r)
    return len(result)


data = {
    'A': (-30, 4),
    'B': (-28, -25),
    'C': (-21, 6),
    'D': (-23, 0),
    'E': (1, 4),
    'F': (-22, -2)
}
do(data)

저도 C++객체구조로 한번 코딩해보았습니다. 그냥 아이스크림을 넣으면 냉장고 중에 넣을수 있는 애가 있는지 검사하고 넣을 수 있으면 넣고 안되면 새로 냉장고 만들어서 넣는 식인데, 너무 단순하게 짜서 오류가 있을 수도 있을 것 같아서 올려보아요.

#include <list>

class IceCream
{
public:
    IceCream() {}
    IceCream(int min, int max) : minTemp(min), maxTemp(max) {};
    ~IceCream() {};
    int minTemp;
    int maxTemp;
};


class Refridgerator
{
public:
    std::list<IceCream> having;
    int minTemp = -100000;
    int maxTemp = 100000;

    Refridgerator() {};
    ~Refridgerator() {};

    bool CanPutIceCream(IceCream iceCream) {
        //범위에 들어오는지 검사 //문제 조건에서 경계도 가능한 것 같다
        if (this->minTemp <= iceCream.maxTemp && this->maxTemp >= iceCream.minTemp)
            return true;
        else return false;
    }
    void Put(IceCream iceCream)
    {
        if (iceCream.minTemp > this->minTemp)
        {
            this->minTemp = iceCream.minTemp;
        }
        if (iceCream.maxTemp < this->maxTemp)
        {
            this->maxTemp = iceCream.maxTemp;
        }
        having.push_back(iceCream);
    }

};

class GivemeThatIceCream
{
public:
    GivemeThatIceCream();
    ~GivemeThatIceCream();

    std::list<Refridgerator> refridList;

    void PushIceCream(IceCream iceCream)
    {
        bool havePushed = false;
        for each (auto refr in refridList)
        {
            if (refr.CanPutIceCream(iceCream))
            {
                refr.Put(iceCream);
                havePushed = true;
                break;
            }
        }

        if (havePushed == false)
        {
            Refridgerator newRefr;
            refridList.push_back(newRefr);
            refridList.back().Put(iceCream);
            havePushed = true;
        }
    }

    int RefridgeNum() { return refridList.size(); }
};

재귀를 이용한 모든 경우의 수를 구하는 노가다.....

아이스크림 종류 수 n : 4

min, max 순서로 입력

-20 -15

-14 -5

-18 -13

-5 -3

result : 2

계속하려면 아무 키나 누르십시오 . . .

#include <stdio.h>
#include <stdlib.h>
struct Icecream {
    int min;
    int max;
    bool flag;
}* ic;

int n;

void init();
int grouping(int val, int count);
bool verdict();

void main() {
    n = 4;
    printf("아이스크림 종류 수 n : ");
    scanf("%d", &n);
    ic = (Icecream*) malloc (sizeof(Icecream) * n);
    init();
    int result = 0;
    for(int i=0;i<1;i++)
        result = grouping(i, 0);
    printf("\nresult : %d\n", result);

}

void init() {
    for(int i=0;i<n;i++)
        ic[i].flag = false;
    printf("min, max 순서로 입력\n");
    for(int i=0;i<n;i++)
        scanf("%d %d", &ic[i].min, &ic[i].max);
}

int grouping(int val, int count) {
    for(int i=0;i<n;i++) {
        if((ic[val].min<=ic[i].min && ic[val].max >= ic[i].min) || (ic[val].min<= ic[i].max && ic[val].max >= ic[i].max)) {
            ic[i].flag = true;
        }
    }
    count++;
    if(!verdict()) {
        for(int i=0;i<n;i++) {
            if(ic[i].flag == false)
                count = grouping(i, count);
        }
    }

    return count;
}

bool verdict() { // false 는 아직 루프가 필요
    for(int i=0;i<n;i++)
        if(ic[i].flag == false)
            return false;
    return true;
}

가장 높은 하한(lmax)을 포함하는 최적해가 항상 존재합니다.

1. t_a >= t_b >= lmax일때, t_a 으로 저장할 수 있는 아이스크림의 집합은 tb의 그것의 부분집합입니다.
2. 만약 lmax보다 낮은 온도 밖에 없다면, lmax를 하한으로 갖는 아이스크림을 보관하지 못하므로 해가 아닙니다.
3. 만약 lmax보다 높은 온도가 t1, t2, ..., tn (t1 < t2 < t3 < ...)로 여러 개 있다면, 1에 의해서 t2..tn은 필요가 없기 때문에 최적해가 아닙니다.
4. 2-1과 2-2에 의하여 최적해는 t >= lmax인 t를 한 개만 포함해야 합니다. 그런데 t >= lmax >= lmax이므로 1에 의해 t를 lmax로 바꿔도 상관이 없습니다. 최적해는 항상 존재하므로 lmax를 포함하는 최적해도 항상 존재합니다.

그러니까 solution(아이스크림들) = {lmax} U solution(lmax로 보관할 수 없는 아이스크림들)입니다.

import Data.Ix


solution = length . takeWhile (/=[]) . iterate (filter =<< fmap not . flip inRange . maximum . fmap fst)

main = print $ solution [(-20, -15), (-14, -5), (-18, -13), (-5, -3)]

def icecream(*v):
    v = sorted(v)
    joint = []

    tmp = [v.pop(0)]
    while 1:
        if isjoint(*tmp, v[0]):
            tmp.append(v.pop(0))
        else:
            joint.append(tmp)
            tmp = [v.pop(0)]
        if not v:
            joint.append(tmp)
            break

    return len(joint)

def isjoint(*v):
    tmp = tuple(zip(*v))
    if max(tmp[0]) <= min(tmp[1]): return True
    else                         : return False

inp = [(-20,-15), (-14,-5), (-18,-13), (-5,-3)]
print(icecream(*inp))

icecreams = [(-20, -15), (-14, -5), (-18, -13), (-5, -3)]
#icecreams = [(-10, 0), (-10, 0), (-1, 0), (-15, -2), (-15, -2), (-15, -1)]

icecreams.sort(key=lambda x: x[0])
n_frz, t_frz = 0, icecreams[0][0] - 1
for low, high in icecreams:
    if low > t_frz:
        n_frz += 1
        t_frz = high

print(n_frz)

품목의 개수를 먼저 입력하고 온도값을 입력합니다. ex) -15 -20

최저 온도를 기준으로 정렬 후, 첫번 째 품목의 최고 온도를 key값으로 설정합니다.

다음 품목을 확인 할 때는 두 가지를 확인합니다.

1. 최고온도가 key값 보다 작은 지 => 새로운 key값 설정

2. 최저온도가 key값 보다 큰 지 => 새로운 냉장고 설정, 새로운 key값 설정

num = int(input())
lst = []
for i in range(num) :
    x = list(map(int,input().split(' ')))
    lst.append(x)
lst.sort(key=lambda x : x[0])
print(lst)

count = 1
key = lst[0][1]
for i in lst :
    if i[1] < key :
        i[1] = key

    if i[0] > key :
        count = count + 1
        key = i[1]

print(count)